{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Substring Without Repeating Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lengthOfLongestSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #无重复字符的最长子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <code>s</code> ，请你找出其中不含有重复字符的&nbsp;<strong>最长子串&nbsp;</strong>的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"abcabcbb\"\n",
    "<strong>输出: </strong>3 \n",
    "<strong>解释:</strong> 因为无重复字符的最长子串是 <code>\"abc\"</code>，所以其长度为 3。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"bbbbb\"\n",
    "<strong>输出: </strong>1\n",
    "<strong>解释: </strong>因为无重复字符的最长子串是 <code>\"b\"</code>，所以其长度为 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = \"pwwkew\"\n",
    "<strong>输出: </strong>3\n",
    "<strong>解释: </strong>因为无重复字符的最长子串是&nbsp;<code>\"wke\"</code>，所以其长度为 3。\n",
    "&nbsp;    请注意，你的答案必须是 <strong>子串 </strong>的长度，<code>\"pwke\"</code>&nbsp;是一个<em>子序列，</em>不是子串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;由英文字母、数字、符号和空格组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-substring-without-repeating-characters](https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-substring-without-repeating-characters](https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcabcbb\"', '\"bbbbb\"', '\"pwwkew\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        res = 0\n",
    "        left = 0 \n",
    "        dic = {}\n",
    "        for right, val in enumerate(s):\n",
    "            dic[val] = dic.get(val, 0) + 1\n",
    "            if len(dic) > k:\n",
    "                va = s[left]\n",
    "                while len(dic) > k:\n",
    "                    va = s[left]\n",
    "                    dic[va] -= 1\n",
    "                    if dic[va] == 0:\n",
    "                        del dic[va]\n",
    "                    left += 1\n",
    "            else:\n",
    "                res = max(res, right - left + 1)\n",
    "        return res\n",
    "                   \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        mySet = set(s)\n",
    "        m, res = len(s), 0\n",
    "        l, r = 0, 1\n",
    "        while r <= m:\n",
    "            while len(set(s[l: r])) > k:\n",
    "                l += 1\n",
    "            res = max(res, len(s[l: r]))\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        #贪心算法+区间搜索\n",
    "        #从左往右探索，最多k个字符串，超出的时候断开\n",
    "        #左侧移动吐出一个字符串（该字符的右侧索引最小），右侧继续探索\n",
    "        if len(s)==0 or k==0:return 0\n",
    "        d_has={}#记录当前的字符在当前选取的字符串中最右侧的index\n",
    "        l=0\n",
    "        r=0\n",
    "        l_c=s[0]#当前字串最左侧字符\n",
    "        d_has[l_c]=0\n",
    "        n=1\n",
    "        ret=\"\"\n",
    "        while l<=r and r <len(s):\n",
    "            #print(\"now:\",l,r,ret,n)\n",
    "            c=s[r]\n",
    "            if (c not in d_has or d_has[c]==-1): #可能存在c被吐出去了\n",
    "                if n==k: #如果算上当前字符，则超出了k\n",
    "                    if ret==\"\" or len(ret)<r-l:\n",
    "                        ret=s[l:r]\n",
    "                    #print(l,r,s[l:r])\n",
    "                    #左侧指针开始移动，至少要吐出一个字符\n",
    "                    l_min=d_has[s[l]]\n",
    "                    ret_before=\"\"\n",
    "                    while l<=l_min: #l指针移动，一定会存在移动到某位置时，此字符max_index=当前index\n",
    "                        # print(l,l_min,r)\n",
    "                        if d_has[s[l]]<=d_has[l_c]:\n",
    "                            l_min=d_has[s[l]]\n",
    "                        l=l+1\n",
    "                    d_has[s[l-1]]=-1 #已吐出去的字符\n",
    "                    l_c=s[l]\n",
    "                    #print(ret_before)\n",
    "                    ret=ret_before+ret #前面可能会保留部分字符\n",
    "                    #处理当前新增的这个字符信息\n",
    "                    d_has[c]=r\n",
    "                    #n=n-1+1 #左侧吐出了一个，当前新增了一个\n",
    "                else:\n",
    "                    d_has[c]=r\n",
    "                    n=n+1\n",
    "            else:\n",
    "                d_has[c]=r\n",
    "            r=r+1\n",
    "        #最后一次遍历结束的字符串，有可能也满足条件\n",
    "        if n<=k and len(ret)<r-l:\n",
    "            ret=s[l:]\n",
    "        #print (ret)\n",
    "        return len(ret)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        dic = collections.defaultdict(int)\n",
    "        for right, ch in enumerate(s):\n",
    "            dic[ch] += 1\n",
    "            while len(dic) > k:\n",
    "                dic[s[left]] -= 1\n",
    "                if dic[s[left]] == 0:\n",
    "                    del dic[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if len(s) <= k:\n",
    "            return len(s)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        tp_dict = {}\n",
    "        n = len(s)\n",
    "        l = 0\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if s[i] in tp_dict:\n",
    "                tp_dict[s[i]] = i\n",
    "            elif len(tp_dict) == k:\n",
    "                min_v = min(tp_dict.values())\n",
    "                key = [i for i, v in tp_dict.items() if v == min_v ][0]\n",
    "                del tp_dict[key]\n",
    "                tp_dict[s[i]] = i\n",
    "                l = min_v + 1\n",
    "            else:\n",
    "                tp_dict[s[i]] = i\n",
    "            res = max(i - l + 1, res)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        max_len = 0\n",
    "        count = {}\n",
    "        left = right = 0 \n",
    "\n",
    "        while right < len(s):\n",
    "            if s[right] not in count:\n",
    "                count[s[right]] = 0\n",
    "            count[s[right]] += 1\n",
    "\n",
    "            while len(count) > k:\n",
    "                count[s[left]] -= 1\n",
    "                if count[s[left]] == 0:\n",
    "                    del count[s[left]]\n",
    "                left += 1\n",
    "            max_len = max(max_len, right - left + 1)\n",
    "            right += 1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        start=0\n",
    "        n=len(s)\n",
    "        hashmap=dict()\n",
    "        max_len=0\n",
    "\n",
    "        for end in range(n):\n",
    "            hashmap[s[end]]=hashmap.get(s[end],0)+1\n",
    "            if len(hashmap)<=k:\n",
    "                max_len=max(max_len,end-start+1)\n",
    "            else:\n",
    "                while len(hashmap)>k:\n",
    "                    head=s[start]\n",
    "                    hashmap[head]-=1\n",
    "                    if hashmap[head]==0:\n",
    "                        del hashmap[head]\n",
    "                    start+=1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0: return 0\n",
    "        if len(s) <= k:\n",
    "            return len(s)\n",
    "        max_length = k\n",
    "        sub_s = [s[i] for i in range(k)]\n",
    "        for i in range(k, len(s)):\n",
    "            sub_s.append(s[i])\n",
    "            set_sub_s = set(sub_s)\n",
    "            if len(set_sub_s) > k:\n",
    "                sub_s.pop(0)\n",
    "            elif len(sub_s) >= max_length:\n",
    "                max_length = len(sub_s)\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        \n",
    "        left, right = 0, 0\n",
    "        cur_dict = collections.defaultdict(int)\n",
    "        result = ''\n",
    "\n",
    "        while right < len(s):\n",
    "            char = s[right]\n",
    "            cur_dict[char] += 1\n",
    "            right += 1\n",
    "            if len(cur_dict) <= k and len(s[left:right]) > len(result):\n",
    "                result = s[left:right]\n",
    "            while len(cur_dict) > k:\n",
    "                char_to_remove = s[left]\n",
    "                cur_dict[char_to_remove] -= 1\n",
    "                if cur_dict[char_to_remove] == 0:\n",
    "                    del cur_dict[char_to_remove]\n",
    "                left +=1\n",
    "        return len(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        length = len(s)\n",
    "        if (length == 0):\n",
    "            return 0\n",
    "        left = 0\n",
    "        max_len = 0\n",
    "        for i in range(length):\n",
    "            while(len(set(s[left:i+1]))>k):\n",
    "                left+=1\n",
    "            max_len = max(max_len,len((s[left:i+1])))\n",
    "        return max_len\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s, k) :\n",
    "        n = len(s) \n",
    "        if k == 0 or n == 0:\n",
    "            return 0\n",
    "        \n",
    "        # sliding window left and right pointers\n",
    "        left, right = 0, 0\n",
    "        # hashmap character -> its rightmost position \n",
    "        # in the sliding window\n",
    "        hashmap = {}\n",
    "\n",
    "        max_len = 1\n",
    "        \n",
    "        while right < n:\n",
    "            # add new character and move right pointer\n",
    "            hashmap[s[right]] = right\n",
    "            right += 1\n",
    "\n",
    "            # slidewindow contains 3 characters\n",
    "            if len(hashmap) == k + 1:\n",
    "                # delete the leftmost character\n",
    "                del_idx = min(hashmap.values())\n",
    "                del hashmap[s[del_idx]]\n",
    "                # move left pointer of the slidewindow\n",
    "                left = del_idx + 1\n",
    "\n",
    "            max_len = max(max_len, right - left)\n",
    "\n",
    "        return max_len\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if True:\n",
    "            slow, fast = 0,0\n",
    "            cur_len, max_len = 0,0\n",
    "            while fast<len(s):\n",
    "                if len(set(s[slow:fast+1]))<=k:\n",
    "                    cur_len = fast-slow+1\n",
    "                    max_len = max(cur_len, max_len)\n",
    "                    fast +=1\n",
    "                else:\n",
    "                    slow +=1\n",
    "            return max_len\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        else:\n",
    "\n",
    "            if not isinstance(s, str):\n",
    "                return 0\n",
    "\n",
    "            def check_str(str1, k):\n",
    "                return len(set(str1))<=k\n",
    "\n",
    "            results = []\n",
    "            left, right = 0,0\n",
    "            while True:\n",
    "                if check_str(s[left:right+1], k):\n",
    "                    results.append(s[left:right+1])\n",
    "                    right +=1\n",
    "                else:\n",
    "                    left +=1\n",
    "                if right == len(s):\n",
    "                    break\n",
    "\n",
    "            results.sort(key=len, reverse=True)\n",
    "            if results:\n",
    "                return len(results[0])\n",
    "            else:\n",
    "                return 0\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "\n",
    "\n",
    "        window = {}\n",
    "        maxlen = float('-inf')\n",
    "        l = 0\n",
    "\n",
    "        for r in range(len(s)):\n",
    "            c = s[r]\n",
    "            window[c] = window.get(c, 0) + 1\n",
    "            while len(window) > k:\n",
    "                window[s[l]] -= 1\n",
    "                if window[s[l]] == 0:\n",
    "                    del window[s[l]]\n",
    "                l += 1\n",
    "            maxlen = max(maxlen, r -  l + 1)\n",
    "        \n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Moving window. Time O(n) Space O(1)\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        window = {}\n",
    "        l, r = 0, 0\n",
    "        res = 0\n",
    "        while r < n:\n",
    "            window[s[r]] = window.get(s[r], 0) + 1\n",
    "            while len(window) > k:\n",
    "                window[s[l]] = window.get(s[l], 0) - 1\n",
    "                if window[s[l]] == 0:\n",
    "                    window.pop(s[l])\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k) -> int:\n",
    "        if not k:\n",
    "            return 0\n",
    "        left = 0\n",
    "        max_count = 0\n",
    "        record = {}\n",
    "        for i in range(len(s)):\n",
    "            record[s[i]] = i\n",
    "            if len(record)>k:\n",
    "                max_count = max(max_count, i-left)\n",
    "                left = min(record.values())+1\n",
    "                tmp = None\n",
    "                for kk in record:\n",
    "                    if record[kk] == left-1:\n",
    "                        tmp = kk\n",
    "                        break\n",
    "                record.pop(tmp)\n",
    "        max_count = max(max_count, max(record.values())-left+1)\n",
    "        return max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        right = 0\n",
    "        left = 0\n",
    "        window = {}\n",
    "        non_zore = 0\n",
    "        res = 0\n",
    "\n",
    "        while right <len(s):\n",
    "            in_curr = s[right]\n",
    "            if in_curr not in window:\n",
    "                window[in_curr] = 1\n",
    "                non_zore += 1\n",
    "            else:\n",
    "                if window[in_curr] == 0:\n",
    "                    non_zore += 1\n",
    "                window[in_curr] += 1\n",
    "            right += 1\n",
    "\n",
    "            while non_zore > k:\n",
    "                out_curr = s[left]\n",
    "                window[out_curr] -= 1\n",
    "                if window[out_curr] == 0:\n",
    "                    non_zore -= 1\n",
    "                left += 1\n",
    "            res = max(res, right - left)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        #滑动窗口，左右指针，右指针的元素放到字典中，并记录字符出现的次数，循环条件，右指针不超过\n",
    "        #字符串长度，\n",
    "\n",
    "        l,r =0,0\n",
    "        res_dict={}\n",
    "        max_len=0\n",
    "\n",
    "        while r<len(s):\n",
    "            #如果s[r]已经出现过，基数加1，否则的话，初始化为1\n",
    "            res_dict[s[r]]=res_dict.get(s[r],0)+1\n",
    "            while len(res_dict)>k:\n",
    "                res_dict[s[l]]-=1\n",
    "                if res_dict[s[l]]==0:\n",
    "                    del res_dict[s[l]]\n",
    "                l+=1\n",
    "            max_len=max(max_len,r-l+1)\n",
    "            r+=1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k==0 or s=='':\n",
    "            return 0\n",
    "        slow,fast=0,0\n",
    "        longest=0\n",
    "        hashmap={}\n",
    "        window_count=0\n",
    "        distinct_count=0\n",
    "        while fast<len(s):\n",
    "            hashmap[s[fast]]=hashmap.get(s[fast],0)+1\n",
    "            while len(hashmap)>k:\n",
    "                hashmap[s[slow]]-=1\n",
    "                if hashmap[s[slow]]==0:\n",
    "                    del hashmap[s[slow]]\n",
    "                slow+=1\n",
    "            longest=max(longest,fast-slow+1)\n",
    "            fast+=1\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        max_len = 0\n",
    "        start = 0\n",
    "        hashmap = {}\n",
    "        \n",
    "        for end in range(len(s)):\n",
    "            tail  = s[end]\n",
    "            if tail in hashmap:\n",
    "                hashmap[tail]+=1\n",
    "            else:\n",
    "                hashmap[tail] = 1\n",
    "            if len(hashmap)<=k:\n",
    "                max_len = max(max_len,end-start+1)\n",
    "        \n",
    "            while len(hashmap)>k:\n",
    "                head = s[start]\n",
    "                hashmap[head]-=1\n",
    "                if hashmap[head]==0:\n",
    "                    del hashmap[head]\n",
    "                start+=1\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        l,mask,ans=0,[0]*300,0\n",
    "        cnt=0\n",
    "        for r in range(n):\n",
    "            mask[ord(s[r])-97]+=1\n",
    "            if mask[ord(s[r])-97]==1:\n",
    "                cnt+=1\n",
    "            while l<=r and cnt>k:\n",
    "                mask[ord(s[l])-97]-=1\n",
    "                if mask[ord(s[l])-97]==0: cnt-=1\n",
    "                l+=1\n",
    "            ans=max(ans,r-l+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n < k+1:\n",
    "            return n\n",
    "        winfreq={}\n",
    "        for c in s:\n",
    "            winfreq[c] = 0\n",
    "        left, right = 0, 0\n",
    "        res = k\n",
    "        count = 0\n",
    "        while right < n:\n",
    "            winfreq[s[right]] += 1\n",
    "            if winfreq[s[right]] == 1:\n",
    "                count += 1\n",
    "            right += 1\n",
    "            while count == k+1:\n",
    "                winfreq[s[left]] -= 1\n",
    "                if winfreq[s[left]] == 0:\n",
    "                    count -= 1\n",
    "                left += 1\n",
    "            res = max(res, (right-left))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        start, max_length, chat_count = 0,0,{}\n",
    "\n",
    "        for end in range(len(s)):\n",
    "            chat_count[s[end]] = chat_count.get(s[end], 0) + 1\n",
    "\n",
    "            while len(chat_count) > k:\n",
    "                chat_count[s[start]] -= 1\n",
    "                if chat_count[s[start]] == 0:\n",
    "                    del chat_count[s[start]]\n",
    "                start += 1\n",
    "            \n",
    "            max_length = max(max_length, end - start +1)\n",
    "        \n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "\n",
    "        unique_count = 0 #how many unique char\n",
    "        dic = defaultdict(int) #粗出目前每个字母的count\n",
    "\n",
    "        max_len = 0 \n",
    "\n",
    "        left , right = 0, 0 \n",
    "\n",
    "        while right <len(s):\n",
    "\n",
    "            if dic[s[right]] == 0:\n",
    "                unique_count +=1\n",
    "            dic[s[right]] +=1\n",
    "            right +=1\n",
    "\n",
    "            while unique_count>k:\n",
    "                if dic[s[left]] ==1:\n",
    "                    unique_count -=1\n",
    "                dic[s[left]] -=1\n",
    "                left +=1\n",
    "            \n",
    "            max_len= max(max_len,right-left)\n",
    "        \n",
    "        return max_len\n",
    "\n",
    "\n",
    "#         时间复杂度\n",
    "# 我们遍历了整个字符串 s，这个操作的时间复杂度是 O(len(s))。\n",
    "# 字典查找和更新操作的时间复杂度都是 O(1)。\n",
    "# 所以，总的时间复杂度是 O(len(s))。\n",
    "\n",
    "# 空间复杂度\n",
    "# 我们使用了一个额外的字典 dic 来存储每个字符出现的次数，这个字典的大小最多与 s 的长度相等。\n",
    "# 因此，总的空间复杂度是 O(len(s))。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        dic = {}\n",
    "        left = 0\n",
    "        right = 0\n",
    "        curr_max = 0\n",
    "        while right < len(s):\n",
    "            dic[s[right]] = dic.get(s[right], 0) + 1\n",
    "            while len(dic) > k:\n",
    "                dic[s[left]] -= 1\n",
    "                if dic[s[left]] == 0:\n",
    "                    dic.pop(s[left])\n",
    "                left += 1\n",
    "            curr_max = max(curr_max, right - left + 1)\n",
    "            right += 1\n",
    "        return curr_max\n",
    "            \n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        if k == 0 or not s:\n",
    "            return 0\n",
    "        \n",
    "        cnter = defaultdict(int)\n",
    "        left_idx = 0\n",
    "        right_idx = 1\n",
    "        cnter[s[left_idx]] += 1\n",
    "        ret_max = 1\n",
    "\n",
    "        while right_idx < len(s):\n",
    "            cnter[s[right_idx]] += 1\n",
    "            right_idx += 1\n",
    "            if len(cnter) <= k:\n",
    "                candidate = right_idx - left_idx\n",
    "                if candidate > ret_max:\n",
    "                    ret_max = candidate\n",
    "            else:\n",
    "                while len(cnter) > k:\n",
    "                    cnter[s[left_idx]] -= 1\n",
    "                    if cnter[s[left_idx]] == 0:\n",
    "                        cnter.pop(s[left_idx])\n",
    "                    left_idx += 1\n",
    "        \n",
    "        return ret_max\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        \n",
    "        length_of_string            = len(s)\n",
    "        hash_dict                   = collections.defaultdict(int)  # key: letter ; value: maximum position of certain letter\n",
    "        left_pointer, right_pointer = 0, -1\n",
    "        max_length                  = 0\n",
    "\n",
    "        while right_pointer+1 <= length_of_string-1:\n",
    "            \n",
    "            # 1. \n",
    "            right_pointer               += 1\n",
    "            hash_dict[s[right_pointer]] = right_pointer\n",
    "\n",
    "            # 2.\n",
    "            if len(hash_dict) == k+1:\n",
    "                minimum_position = min(hash_dict.values())\n",
    "\n",
    "                for letter, position in hash_dict.items():\n",
    "                    if position == minimum_position:\n",
    "                        minimum_position_letter = letter\n",
    "                \n",
    "                del hash_dict[minimum_position_letter]\n",
    "                left_pointer = minimum_position + 1\n",
    "\n",
    "            # 3.\n",
    "            max_length = max(max_length, right_pointer - left_pointer + 1)\n",
    "\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        n = len(s)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        res = 0\n",
    "        left = right = 0\n",
    "        while right < n:\n",
    "            cnt[s[right]] += 1\n",
    "            while len(cnt) > k:\n",
    "                cnt[s[left]] -= 1\n",
    "                if cnt[s[left]] == 0:\n",
    "                    del cnt[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        \n",
    "        # left , right = 0 , 0#初始化左右指针0,0\n",
    "\n",
    "        # max_len = 0 \n",
    "\n",
    "        # #要同时记录目前为止出现了几个unique字符，和每个字符出现的次数\n",
    "        # # dic的意义在于，控制左指针是否继续往右移动。\n",
    "        # #例如eceba。 当右指针指向b，已经用了4个。此时左指针应该移动了。而e已经累计2次了，左指针目前指向e。先判断e一共出现几次，是2次，因此移动1次后还不够完全去除这个e的出现。 因此只能把出现次数减1. 此时left向右移动一次指向c，\n",
    "        # # dic = {\"e\": 1, \"c\": 1, \"b\": 1}\n",
    "        #  #由于uniuqe_count还是3>2继续移动，c只出现了一次，移除后unique_count确实-1， 也可以达到2，同时出现次数也-1，left此时移动指向e\n",
    "        #  #dic = {\"e\": 1, \"c\": 0, \"b\": 1}\n",
    "        # # 移动一次，e的次数从2 变成1，在移动一次还是不够k，在移动一次，e变成0了，这样unique_count才能顺利-1，达到只用了k个的目的\n",
    "        # unique_count =0 \n",
    "        # dic = defaultdict(int)\n",
    "\n",
    "\n",
    "        # while right < len(s):\n",
    "        #     if dic[s[right]] == 0: #如果未出现过，说明应该记录一次uniquecount\n",
    "        #         unique_count +=1\n",
    "        #     dic[s[right]] +=1 #记录此字符出现的次数\n",
    "        #     right +=1 #右指针移动\n",
    "\n",
    "        #     while unique_count > k:\n",
    "        #         if dic[s[left]] ==1: #如过\n",
    "        #             unique_count -= 1\n",
    "        #         dic[s[left]] -= 1 \n",
    "                \n",
    "        #         left += 1 \n",
    "\n",
    "                \n",
    "        #     max_len = max(max_len, right -left) #每次都更新max len\n",
    "            \n",
    "        # return max_len\n",
    "\n",
    "\n",
    "#左右指针，超过k个就移动左，\n",
    "#要用unique字母计数器， 单个字母计数器\n",
    "\n",
    "\n",
    "\n",
    "        #max lend 就是left-right\n",
    "        # 时刻控制l r 在合法范围\n",
    "        # 需要一个uniuqe count记录几个唯一字母\n",
    "\n",
    "        # 还需要记录每个字母目前出现了几次，以控制unique count的增减\n",
    "\n",
    "\n",
    "\n",
    "        left,right = 0, 0\n",
    "        max_len = 0\n",
    "        dic = defaultdict(int)#no intialize\n",
    "        unique_count = 0\n",
    "\n",
    "        while right < len(s):\n",
    "\n",
    "            if dic[s[right]] ==0: #dic默认是0 \n",
    "                unique_count +=1\n",
    "            dic[s[right]] +=1\n",
    "            right +=1\n",
    "\n",
    "            while unique_count >k: \n",
    "                if dic[s[left]]==1:\n",
    "                    unique_count -=1\n",
    "                dic[s[left]] -=1\n",
    "                left +=1\n",
    "\n",
    "            max_len = max(max_len, right -left)\\\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "\n",
    "        hashmap = {}\n",
    "\n",
    "        wordset = set() \n",
    "\n",
    "        i = 0\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        j = 0\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while j < len(s):\n",
    "\n",
    "            cur_char = s[j]\n",
    "            if cur_char not in hashmap:\n",
    "                hashmap[cur_char] = 1\n",
    "                count += 1\n",
    "            else:\n",
    "                hashmap[cur_char] += 1\n",
    "\n",
    "\n",
    "            while count > k:\n",
    "                cur_char = s[i]\n",
    "\n",
    "                if cur_char in hashmap:\n",
    "                    hashmap[cur_char] -= 1\n",
    "                    if hashmap[cur_char] == 0:\n",
    "                        del hashmap[cur_char]\n",
    "                        count -= 1\n",
    "                    \n",
    "                i += 1\n",
    "\n",
    "            res = max(res, j - i + 1)\n",
    "\n",
    "            j += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k==0:\n",
    "            return 0\n",
    "        start = 0\n",
    "        max_len = 0\n",
    "        h = dict()\n",
    "        count_set=set()\n",
    "        length = list()\n",
    "        for n in range(len(s)):\n",
    "            h[s[n]] = h.get(s[n],0)+1\n",
    "            if  len(h)<=k:\n",
    "                max_len= max(n-start+1, max_len)\n",
    "            while len(h)>k:\n",
    "                h[s[start]] -= 1\n",
    "                if h.get(s[start])==0:\n",
    "                    del  h[s[start]]\n",
    "                start += 1               \n",
    "        return max_len        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        d, res, l = defaultdict(int), 0, 0\n",
    "        for r, c in enumerate(s):\n",
    "            d[c] += 1\n",
    "            while len(d) > k:\n",
    "                d[s[l]] -= 1\n",
    "                if d[s[l]] == 0:\n",
    "                    d.pop(s[l])\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        cache = {}\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            cache[c] = cache.get(c, 0) + 1\n",
    "            while len(cache) > k:\n",
    "                left_c = s[left]\n",
    "                cache[left_c] -= 1\n",
    "                if not cache[left_c]:\n",
    "                    del cache[left_c]\n",
    "                left += 1\n",
    "            res = max(res, i - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        left,right=0,0\n",
    "        used=dict()\n",
    "        if k==0:\n",
    "            return 0\n",
    "        max_lenth=0\n",
    "        while right<len(s):\n",
    "            if s[right] in used:\n",
    "                used[s[right]]=right\n",
    "                right+=1\n",
    "                max_lenth=max(max_lenth,right-left)\n",
    "            elif s[right] not in used:\n",
    "                if len(used)<k:\n",
    "                    used[s[right]]=right\n",
    "                    right+=1\n",
    "                    max_lenth=max(max_lenth,right-left)\n",
    "                else:\n",
    "                    min_key=None\n",
    "                    min_index=1000000\n",
    "                    for key,val in used.items():\n",
    "                        if val<min_index:\n",
    "                            min_key=key\n",
    "                            min_index=val\n",
    "                    left=min_index+1\n",
    "                    used.pop(min_key)\n",
    "                    used[s[right]]=right\n",
    "                    right+=1\n",
    "                    max_lenth=max(max_lenth,right-left)\n",
    "        \n",
    "        return max_lenth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        for r,x in enumerate(s):\n",
    "            cnt[x] += 1\n",
    "            while len(cnt) > k:\n",
    "                cnt[s[l]] -= 1\n",
    "                if not cnt[s[l]]:\n",
    "                    cnt.pop(s[l])\n",
    "                l += 1\n",
    "            ans = max(ans,r - l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        max_len = 0\n",
    "        d = {}\n",
    "        start = 0\n",
    "        for end in range(len(s)):\n",
    "            tail = s[end]\n",
    "            if tail in d:\n",
    "                d[tail]+=1\n",
    "            else:\n",
    "                d[tail]=1\n",
    "            if len(d)<=k:\n",
    "                max_len = max(max_len,end-start+1)\n",
    "            while len(d)>k:\n",
    "                head = s[start]\n",
    "                d[head] -= 1\n",
    "                if d[head] == 0:\n",
    "                    del d[head]\n",
    "                start+=1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        ### solution\n",
    "        # sliding window + hash\n",
    "        # sliding window + ordereddict\n",
    "\n",
    "        ## sw + ordereddict\n",
    "        n = len(s)\n",
    "        i = j = 0\n",
    "        res = 0\n",
    "        od = collections.OrderedDict()\n",
    "        numCha = 0\n",
    "        while j < n:\n",
    "            if s[j] in od:\n",
    "                del od[s[j]]\n",
    "            od[s[j]] = j\n",
    "            if len(od) > k:\n",
    "                c, idx = od.popitem(last=False)\n",
    "                i = idx + 1\n",
    "            res = max(res, j - i + 1)\n",
    "            j += 1\n",
    "        return res\n",
    "\n",
    "        ## sw + hash\n",
    "        n = len(s)\n",
    "        i = j = 0\n",
    "        res = 0\n",
    "        cnt = collections.Counter()\n",
    "        numCha = 0\n",
    "        while j < n:\n",
    "            cnt[s[j]] += 1\n",
    "            if cnt[s[j]] == 1:\n",
    "                numCha += 1\n",
    "            while numCha > k and i <= j:\n",
    "                cnt[s[i]] -= 1\n",
    "                if cnt[s[i]] == 0:\n",
    "                    numCha -= 1\n",
    "                i += 1\n",
    "            res = max(res, j - i + 1)\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "        left = right = 0\n",
    "        n = len(s)\n",
    "        # [left, right]: the longest\n",
    "        res = 0\n",
    "        while right < n:\n",
    "            cnt[s[right]] += 1\n",
    "\n",
    "            while len(cnt) > k:\n",
    "                cnt[s[left]] -= 1\n",
    "                if cnt[s[left]] == 0:\n",
    "                    del cnt[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        dic = {}\n",
    "        l, r = 0, 0\n",
    "        length = 0\n",
    "        n = len(s)\n",
    "        while r<n:\n",
    "            dic[s[r]] = r\n",
    "            while len(dic)>k:\n",
    "                if s[l] in dic and dic[s[l]]==l:\n",
    "                    del dic[s[l]]\n",
    "                l+=1\n",
    "            r+=1\n",
    "            if r-l>length:\n",
    "                length =r-l\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        cache = {}\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            cache[c] = cache.get(c, 0) + 1\n",
    "            while len(cache) > k:\n",
    "                cache[s[left]] -= 1\n",
    "                if cache[s[left]] == 0:\n",
    "                    del cache[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, i - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        count = defaultdict(int)\n",
    "        left = right = 0\n",
    "        res = 0\n",
    "        while right < len(s):\n",
    "            count[s[right]] += 1\n",
    "            while len(count) > k:\n",
    "                count[s[left]] -= 1\n",
    "                if count[s[left]] == 0:\n",
    "                    del count[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "            \n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        s_len = len(s)\n",
    "\n",
    "        if s_len < k:\n",
    "            return s_len\n",
    "\n",
    "        left = right = 0\n",
    "\n",
    "        result = float(\"-inf\")\n",
    "        storage = {}\n",
    "\n",
    "        while right < s_len:\n",
    "            storage[s[right]] = right\n",
    "\n",
    "            right += 1\n",
    "\n",
    "            if len(storage) > k:\n",
    "                del_index = min(storage.values())\n",
    "                del storage[s[del_index]]\n",
    "                left = del_index + 1\n",
    "            result = max(result, right - left)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "            ##s = \"eceba\", k = 2， left和right先同时指向第一个e\n",
    "             #   2 指针的思想其实是 \n",
    "            dic = defaultdict(int)  # 用于记录每个字符的出现次数|如果没有key，默认返回0 \n",
    "            left = 0  # 窗口的左边界\n",
    "            right = 0  # 窗口的右边界，从第一位开始\n",
    "            max_len = 0  # 累计记录max len，跟209对比，那个题求min，所以初始化为一个inf。此处求max，就初始化小一点\n",
    "            counter = 0  # 记录distinct字符的数量,我们最多只能有k个，如果超过了，说明left要往右移\n",
    "             #1. \n",
    "            while right < len(s):#右边界不能超过字符串长度,right从0位开始，也就是e\n",
    "                if dic[s[right]] == 0:  # 如果这个字符没在字典里，确实返回0，lookup存的是每个字符出现的次数\n",
    "                    counter += 1  # 那么distinct字符的count加1\n",
    "                dic[s[right]] += 1  # 更新这个字符的出现次数--key value |\n",
    "                #1：dic = {\"e\": 1} 2： \n",
    "                right += 1  # 扩大窗口的右边界\n",
    "\n",
    "           #2.限制条件     # 当distinct的字符数量超过了k说明多了，那么left要往右移动了，【直到】只剩下2个不同字符\n",
    "                while counter > k:  # 如果窗口中不同字符的数量超过k，\n",
    "                    if dic[s[left]] == 1:  # 如果这个字符只出现了一次,那么移动左指针的话，counter里面也会少一个。如果出现n次就直接下一步-1即可，但counter里面unique字符数不会变\n",
    "                        counter -= 1  # 不同字符的数量减1\n",
    "                    dic[s[left]] -= 1  # 先让dic里面计数减掉\n",
    "                    left += 1  # 再移动left向右\n",
    "            # 3.maxlen  不论怎样都做  #只有distinct字符<=2个，我们才会算当前max多长，前面这个counter的while就是避免这个情况\n",
    "                max_len = max(max_len, right - left)  # 更新窗口的最大大小，由于用的max，他只会变多\n",
    "\n",
    "            return max_len #要的就是max\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        left_index=0\n",
    "        right_index=0\n",
    "        max_lens=0\n",
    "        child_string=\"\"\n",
    "        for index in range(len(s)):\n",
    "            child_string=child_string+s[index]\n",
    "            while(len(set(child_string))>k):\n",
    "                child_string=s[left_index:right_index+1]\n",
    "                left_index+=1\n",
    "            if len(child_string)>max_lens:\n",
    "                max_lens=len(child_string)\n",
    "            right_index+=1\n",
    "        return max_lens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        counter = collections.Counter()\n",
    "        result = left = right = 0\n",
    "        while right < n:\n",
    "            while right < n and len(counter) <= k:\n",
    "                counter[s[right]] += 1\n",
    "                right += 1\n",
    "            # print(right, left)\n",
    "            if len(counter) <= k:\n",
    "                result = max(result, right - left)\n",
    "            else:\n",
    "                result = max(result, right - left - 1)\n",
    "            counter[s[left]] -= 1\n",
    "            if not counter[s[left]]:\n",
    "                counter.pop(s[left])\n",
    "            left += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        left = 0\n",
    "        visited = {}\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        for i in range(len(s)):\n",
    "            visited.setdefault(s[i],0)\n",
    "            if visited[s[i]] == 0:\n",
    "                cnt += 1 \n",
    "            visited[s[i]] += 1\n",
    "            while cnt > k and left < i:\n",
    "                visited[s[left]] -= 1\n",
    "                if visited[s[left]] == 0:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "\n",
    "            #print(left,i,visited,cnt)\n",
    "            res = max(res,i - left + 1)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: 'str', k: 'int') -> 'int':\n",
    "        n = len(s) \n",
    "        if k == 0 or n == 0:\n",
    "            return 0\n",
    "        \n",
    "        # sliding window left and right pointers\n",
    "        left, right = 0, 0\n",
    "        # hashmap character -> its rightmost position \n",
    "        # in the sliding window\n",
    "        hashmap = defaultdict()\n",
    "\n",
    "        max_len = 1\n",
    "        \n",
    "        while right < n:\n",
    "            # add new character and move right pointer\n",
    "            hashmap[s[right]] = right\n",
    "            right += 1\n",
    "\n",
    "            # slidewindow contains 3 characters\n",
    "            if len(hashmap) == k + 1:\n",
    "                # delete the leftmost character\n",
    "                del_idx = min(hashmap.values())\n",
    "                del hashmap[s[del_idx]]\n",
    "                # move left pointer of the slidewindow\n",
    "                left = del_idx + 1\n",
    "\n",
    "            max_len = max(max_len, right - left)\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        left, right = 0, 0\n",
    "        ans = 0\n",
    "        \n",
    "        while right < n:\n",
    "            temp = s[left:right+1]\n",
    "            if len(set(temp)) <= k:\n",
    "                ans = max(ans, len(temp))\n",
    "            else:\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        low = 0\n",
    "        max_len = 0\n",
    "        tmp = dict()\n",
    "        for fast in range(len(s)):\n",
    "            tmp[s[fast]] = tmp.get(s[fast],0) + 1\n",
    "            if len(tmp) <= k:\n",
    "                max_len = max(max_len, fast-low+1)\n",
    "            while len(tmp) > k: # 若窗口长度大于字典长度，说明有重复元素，此时应该减少该元素\n",
    "                head = s[low]\n",
    "                tmp[head] -= 1\n",
    "                if tmp[head] == 0:\n",
    "                    del tmp[head]\n",
    "                low += 1\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        window_dict = {}\n",
    "        for i in s:\n",
    "            window_dict[i] = 0\n",
    "\n",
    "\n",
    "        right = 0\n",
    "        left = 0\n",
    "        res = 0\n",
    "        count = 0\n",
    "\n",
    "        while right < len(s):\n",
    "            right_char = s[right]\n",
    "            right += 1\n",
    "\n",
    "            if window_dict[right_char] == 0:\n",
    "                count += 1\n",
    "\n",
    "            window_dict[right_char] += 1\n",
    "\n",
    "            if count <= k:\n",
    "                res = max(res, right - left)\n",
    "\n",
    "            while count > k:\n",
    "                left_char = s[left]\n",
    "                left += 1\n",
    "\n",
    "                if window_dict[left_char] == 1:\n",
    "                    count -= 1\n",
    "\n",
    "                window_dict[left_char] -= 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        hs = {}\n",
    "        if k == 0:return 0\n",
    "\n",
    "        hs[s[0]] = 1\n",
    "        ss = 0\n",
    "        ee = 1\n",
    "        res = 1\n",
    "        while ee < len(s):\n",
    "            if s[ee] in hs:\n",
    "                hs[s[ee]] +=1\n",
    "            else:\n",
    "                hs[s[ee]] = 1\n",
    "\n",
    "            if len(hs) >k:\n",
    "                while ss < ee and len(hs) >k:\n",
    "                    if hs[s[ss]] == 1:\n",
    "                        del hs[s[ss]]\n",
    "                    else:\n",
    "                        hs[s[ss]] -=1\n",
    "                    ss +=1\n",
    "            \n",
    "            res = max(res, ee-ss+1)\n",
    "\n",
    "            ee+=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        l = r = 0\n",
    "        d = dict()\n",
    "        ans = 0\n",
    "        while r < len(s):\n",
    "            if s[r] not in d:\n",
    "                d[s[r]] = 1\n",
    "            else:\n",
    "                d[s[r]] += 1\n",
    "            while len(d.keys()) > k:\n",
    "                if d[s[l]] == 1:\n",
    "                    del d[s[l]]\n",
    "                else:\n",
    "                    d[s[l]] -= 1\n",
    "                l += 1\n",
    "            r += 1\n",
    "            ans = max(ans,r-l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "\n",
    "        p, q = 1, 0\n",
    "\n",
    "        char_dict = defaultdict(int)\n",
    "        # char_dict[s[0]] = 1\n",
    "        max_len = 0\n",
    "        \n",
    "        while p<= len(s):\n",
    "            c = s[p-1]\n",
    "            char_dict[c] +=1\n",
    "            while len(char_dict) > k:\n",
    "                c2rmv = s[q]\n",
    "                char_dict[c2rmv] -=1\n",
    "                if char_dict[c2rmv] == 0:\n",
    "                    del char_dict[c2rmv]\n",
    "                q+=1\n",
    "            max_len = max(p-q, max_len)\n",
    "            p+=1\n",
    "\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        from collections import Counter\n",
    "        left,res =0,0\n",
    "        cnt = Counter()\n",
    "        for right,c in enumerate(s):\n",
    "            cnt[c]+=1\n",
    "            while len(cnt)>k:\n",
    "                cnt[s[left]]-=1\n",
    "                if cnt[s[left]]==0:\n",
    "                    del cnt[s[left]]\n",
    "                left+=1\n",
    "            res=max(res,right-left+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        record = {}\n",
    "        slow = 0\n",
    "        max_len = 0\n",
    "        for fast in range(len(s)):\n",
    "            if s[fast] in record:\n",
    "                record[s[fast]] += 1\n",
    "            else:\n",
    "                record[s[fast]] = 1\n",
    "                while len(record) == k + 1:\n",
    "                    record[s[slow]] -= 1\n",
    "                    if record[s[slow]] == 0:\n",
    "                        record.pop(s[slow])\n",
    "                    slow += 1\n",
    "            max_len = max(max_len, fast - slow + 1)\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0: return 0\n",
    "        if len(s) <= k:\n",
    "            return len(s)\n",
    "        max_length = k\n",
    "        sub_s = [s[i] for i in range(k)]\n",
    "        for i in range(k, len(s)):\n",
    "            sub_s.append(s[i])\n",
    "            set_sub_s = set(sub_s)\n",
    "            if len(set_sub_s) > k:\n",
    "                sub_s.pop(0)\n",
    "            elif len(sub_s) >= max_length:\n",
    "                max_length = len(sub_s)\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        cnt = defaultdict(int)\n",
    "        ans = 0\n",
    "        while r < len(s):\n",
    "            while len(cnt) > k:\n",
    "                cnt[s[l]] -= 1\n",
    "                if cnt[s[l]] == 0:\n",
    "                    del cnt[s[l]]\n",
    "                l += 1\n",
    "            print(l, r)\n",
    "            while r < len(s) and len(cnt) <= k:\n",
    "                ans = max(ans, r - l)\n",
    "                cnt[s[r]] += 1\n",
    "                r += 1\n",
    "            if len(cnt) <= k:\n",
    "                ans = max(ans, r - l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(s):\n",
    "            cnt[x] += 1\n",
    "            while len(cnt) > k:\n",
    "                cnt[s[left]] -= 1\n",
    "                if cnt[s[left]] == 0:\n",
    "                    del cnt[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        ret=1\n",
    "        l=0\n",
    "        if k==0: return 0\n",
    "        p=collections.defaultdict(str)\n",
    "        p[s[0]]=1\n",
    "        for r in range(1,len(s)):\n",
    "            if len(p)<k:\n",
    "                p[s[r]]=p.get(s[r],0)+1\n",
    "            elif s[r] in p:\n",
    "                p[s[r]]=p.get(s[r],0)+1\n",
    "            else:\n",
    "                while(len(p)>=k):\n",
    "                    if p[s[l]]: p[s[l]]-=1\n",
    "                    if not p[s[l]]:\n",
    "                        p.pop(s[l])\n",
    "                    l+=1\n",
    "                p[s[r]]=p.get(s[r],0)+1\n",
    "            ret=max(ret,r-l+1)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        mySet = set(s)\n",
    "        m, res = len(s), 0\n",
    "        l, r = 0, 1\n",
    "        while r <= m:\n",
    "            while len(set(s[l: r])) > k:\n",
    "                l += 1\n",
    "            res = max(res, len(s[l: r]))\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n == 0 or k == 0:\n",
    "            return 0\n",
    "        left, right = 0, 0\n",
    "        max_len = 1\n",
    "        count = collections.defaultdict(int)\n",
    "        while right < n:\n",
    "            count[s[right]] = right\n",
    "            if len(count) == (k + 1):\n",
    "                index = min(count.values())\n",
    "                del count[s[index]]\n",
    "                left = index + 1\n",
    "            max_len = max(max_len, right - left + 1)\n",
    "            right += 1\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        left = 0\n",
    "        res = 0\n",
    "        my_set = defaultdict(int)\n",
    "        for right in range(n):\n",
    "            my_set[s[right]] += 1\n",
    "            if len(my_set.keys()) <= k:\n",
    "                res = max(res, right - left + 1)\n",
    "            while len(my_set.keys()) > k:\n",
    "                my_set[s[left]] -= 1\n",
    "                if my_set[s[left]] == 0:\n",
    "                    del my_set[s[left]]\n",
    "                left += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        left, right, cnt, res = 0, 0, 0, 0\n",
    "        m = defaultdict(int)\n",
    "        while right < len(s):\n",
    "            m[s[right]] += 1\n",
    "            if m[s[right]] == 1:\n",
    "                cnt += 1\n",
    "            right += 1\n",
    "            while left < right and cnt > k:\n",
    "                m[s[left]] -= 1\n",
    "                if m[s[left]] == 0:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            res = max(res, right - left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        #简单计数+滑窗即可\n",
    "        n=len(s)\n",
    "        l,mask,ans=0,[0]*300,0\n",
    "        cnt=0\n",
    "        for r in range(n):\n",
    "            mask[ord(s[r])-97]+=1\n",
    "            if mask[ord(s[r])-97]==1:\n",
    "                cnt+=1\n",
    "            while l<=r and cnt>k:\n",
    "                mask[ord(s[l])-97]-=1\n",
    "                if mask[ord(s[l])-97]==0: cnt-=1\n",
    "                l+=1\n",
    "            ans=max(ans,r-l+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        from collections import OrderedDict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: 'str', k: 'int') -> 'int':\n",
    "        n = len(s) \n",
    "        if k == 0 or n == 0:\n",
    "            return 0\n",
    "        \n",
    "        # sliding window left and right pointers\n",
    "        left, right = 0, 0\n",
    "        # hashmap character -> its rightmost position \n",
    "        # in the sliding window\n",
    "        hashmap = OrderedDict()\n",
    "\n",
    "        max_len = 1\n",
    "        \n",
    "        while right < n:\n",
    "            character = s[right]\n",
    "            # if character is already in the hashmap -\n",
    "            # delete it, so that after insert it becomes\n",
    "            # the rightmost element in the hashmap\n",
    "            if character in hashmap:\n",
    "                del hashmap[character]\n",
    "            hashmap[character] = right\n",
    "            right += 1\n",
    "\n",
    "            # slidewindow contains k + 1 characters\n",
    "            if len(hashmap) == k + 1:\n",
    "                # delete the leftmost character\n",
    "                _, del_idx = hashmap.popitem(last = False)\n",
    "                # move left pointer of the slidewindow\n",
    "                left = del_idx + 1\n",
    "\n",
    "            max_len = max(max_len, right - left)\n",
    "\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        l, r = 0, 0\n",
    "        has = {}\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "\n",
    "            has[s[r]] = has.get(s[r], 0) + 1\n",
    "\n",
    "            while len(has) > k:\n",
    "\n",
    "                has[s[l]] -= 1\n",
    "                if has[s[l]] == 0:\n",
    "                    del has[s[l]]\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        window = defaultdict(int)\n",
    "\n",
    "        res = 0\n",
    "        left, right = 0, 0\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "\n",
    "            window[c] += 1\n",
    "\n",
    "            while len(window) > k:\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                window[d] -= 1\n",
    "                if window[d] == 0:\n",
    "                    window.pop(d)\n",
    "            \n",
    "            res = max(res, right - left)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        visited = collections.defaultdict(int)\n",
    "        l, r = 0, 0\n",
    "        max_len = 0\n",
    "        for r in range(len(s)):\n",
    "            visited[s[r]] += 1\n",
    "            while l < r and len(visited) > k:\n",
    "                if visited[s[l]] == 1:\n",
    "                    del visited[s[l]]\n",
    "                else:\n",
    "                    visited[s[l]] -= 1\n",
    "                l += 1\n",
    "            if r - l + 1 > max_len:\n",
    "                max_len = r - l + 1\n",
    "        \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        left = 0\n",
    "        window = defaultdict(lambda: 0)\n",
    "        type_cnt = 0\n",
    "\n",
    "        res = 0\n",
    "        for right, c in enumerate(s):\n",
    "            window[c] += 1\n",
    "            if window[c] == 1:\n",
    "                type_cnt += 1\n",
    "\n",
    "            while type_cnt> k:\n",
    "                d = s[left]\n",
    "                window[d] -= 1\n",
    "                left += 1\n",
    "\n",
    "                if window[d] == 0:\n",
    "                    type_cnt -= 1\n",
    "            res = max(res, right - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "substring内最多就k个不同的char\n",
    "但是个数小于k也行\n",
    "\"\"\"\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:        \n",
    "        char_to_freq = Counter()\n",
    "        left = 0\n",
    "        res = 0\n",
    "\n",
    "        for right in range(len(s)):\n",
    "            char_to_freq[s[right]] += 1\n",
    "\n",
    "            # window最多只能有k个不同char, 如果个数大于k,就要shrink\n",
    "            while len(char_to_freq) > k:\n",
    "                char_to_freq[s[left]] -= 1\n",
    "                if char_to_freq[s[left]] == 0:\n",
    "                    del char_to_freq[s[left]]\n",
    "                left += 1\n",
    "            \n",
    "            res = max(res, right - left + 1)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        left = ans = 0\n",
    "        meepo = dict()\n",
    "        n = len(s)\n",
    "\n",
    "        for right, ch in enumerate(s):\n",
    "            meepo[ch] = meepo.get(ch, 0) + 1\n",
    "\n",
    "            if len(meepo) > k:        # now, right is actually right + 1\n",
    "                ans = max(ans, right - left) \n",
    "\n",
    "                while len(meepo) > k:       # delete untill there is k distinct chs\n",
    "                    left_ch = s[left]\n",
    "                    meepo[left_ch] -= 1\n",
    "                    if meepo[left_ch] == 0:      # delete empty ch = len(meepo) - 1\n",
    "                        del meepo[left_ch]\n",
    "                    left += 1\n",
    "\n",
    "        # update for the last ch, where right = n-1, length = right-left-1:\n",
    "        ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "\n",
    "        l,r =0,0\n",
    "        res_dict={}\n",
    "        max_len=0\n",
    "\n",
    "        while r<len(s):\n",
    "            res_dict[s[r]]=res_dict.get(s[r],0)+1\n",
    "            while len(res_dict)>k:\n",
    "                res_dict[s[l]]-=1\n",
    "                if res_dict[s[l]]==0:\n",
    "                    del res_dict[s[l]]\n",
    "                l+=1\n",
    "            max_len=max(max_len,r-l+1)\n",
    "            r+=1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k==0 or s=='':\n",
    "            return 0\n",
    "        slow,fast=0,0\n",
    "        longest=0\n",
    "        hashmap={}\n",
    "        window_count=0\n",
    "        distinct_count=0\n",
    "        while fast<len(s):\n",
    "            hashmap[s[fast]]=hashmap.get(s[fast],0)+1\n",
    "            while len(hashmap)>k:\n",
    "                hashmap[s[slow]]-=1\n",
    "                if hashmap[s[slow]]==0:\n",
    "                    del hashmap[s[slow]]\n",
    "                slow+=1\n",
    "            # if len(hashmap)==k:\n",
    "            longest=max(longest,fast-slow+1)\n",
    "            fast+=1\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        n = len(s)\n",
    "        if n < k + 1:\n",
    "            return n\n",
    " \n",
    "        # 滑动窗口的左右指针\n",
    "        left, right = 0, 0\n",
    "        # hashmap 中的字符 -> 它在滑动窗口中最靠右的位置\n",
    "        hashmap = defaultdict()\n",
    " \n",
    "        max_len = k\n",
    " \n",
    "        while right < n:\n",
    "            # 当滑动窗口包含小于 3 个字符\n",
    "            hashmap[s[right]] = right\n",
    "            right += 1\n",
    " \n",
    "            # 滑动窗口包含 3 个字符\n",
    "            if len(hashmap) == k + 1:\n",
    "                # 删除最左边的字符\n",
    "                del_idx = min(hashmap.values())\n",
    "                del hashmap[s[del_idx]]\n",
    "                # 删除滑动窗口的左指针\n",
    "                left = del_idx + 1\n",
    " \n",
    "            max_len = max(max_len, right - left)\n",
    " \n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        maps = collections.defaultdict(int)\n",
    "        n = len(s)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        res = 0\n",
    "        l = r = 0\n",
    "        while r < n:\n",
    "            maps[s[r]] += 1\n",
    "            while len(maps) > k:\n",
    "                maps[s[l]] -= 1\n",
    "                if maps[s[l]] == 0:\n",
    "                    del maps[s[l]]\n",
    "                l += 1\n",
    "            \n",
    "            res = max(res, r-l+1)\n",
    "            r+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        max_length = 0\n",
    "        left = 0\n",
    "        dic = dict()\n",
    "        sett = set()\n",
    "        for right in range(len(s)):\n",
    "            if s[right] in sett:\n",
    "                dic[s[right]] += 1\n",
    "                max_length = max(max_length, right - left + 1)\n",
    "            else:\n",
    "                while left < right and len(sett) == k:\n",
    "                    left_char = s[left]\n",
    "                    dic[left_char] -= 1\n",
    "                    if dic[left_char] == 0:\n",
    "                        del dic[left_char]\n",
    "                        sett.remove(left_char)\n",
    "                    left += 1\n",
    "                dic[s[right]] = 1\n",
    "                sett.add(s[right])\n",
    "                max_length = max(max_length, right - left + 1)\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "      n = len(s)\n",
    "      i = j = 0\n",
    "      res = 0\n",
    "      cnt = collections.Counter() # 计数哈希\n",
    "      numCha = 0 # 窗口里的不同字符的数量\n",
    "      while j < n:\n",
    "          cnt[s[j]] += 1\n",
    "          if cnt[s[j]] == 1: # 有新的字符加入\n",
    "              numCha += 1\n",
    "          while numCha > k and i <= j:\n",
    "              cnt[s[i]] -= 1\n",
    "              if cnt[s[i]] == 0: # 有字符被移除窗口\n",
    "                  del cnt[s[i]] # 也可以不用删除\n",
    "                  numCha -= 1\n",
    "              i += 1\n",
    "          res = max(res, j - i + 1)\n",
    "          j += 1\n",
    "      return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s)==1:\n",
    "            return 1\n",
    "        slow = 0\n",
    "        fast = 1\n",
    "        max_len = 2\n",
    "        res = ''\n",
    "        while fast<len(s)-1:\n",
    "            fast+=1\n",
    "            if len(set(s[slow:fast+1]))>2:\n",
    "                for i in range(slow+1,fast+1):\n",
    "                    if len(set(s[i:fast+1]))==2:\n",
    "                        slow = i\n",
    "                        break\n",
    "            if fast-slow+1>max_len:\n",
    "                res = s[slow:fast+1]\n",
    "                max_len = fast-slow+1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n < 3:\n",
    "            return n\n",
    "\n",
    "        left,right = 0,0\n",
    "        hashmap = defaultdict()\n",
    "        max_len = 2\n",
    "\n",
    "        while right < n:\n",
    "            hashmap[s[right]] = right\n",
    "            right += 1\n",
    "\n",
    "            if len(hashmap) == 3:\n",
    "                del_idx = min(hashmap.values())\n",
    "                del hashmap[s[del_idx]]\n",
    "                left = del_idx + 1\n",
    "\n",
    "            max_len = max(max_len, right - left)\n",
    "\n",
    "        return max_len\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        #至少包含两个不同字符最大子串长度值\n",
    "        right,left=0,0\n",
    "        max_s,temp_s=0,0\n",
    "        hashmap=Counter()\n",
    "        for right,x in enumerate(s):\n",
    "            hashmap[x]+=1\n",
    "            if len(hashmap) ==2:\n",
    "                #哈希表长度为2的时候表明只有两个不同字符，更新max\n",
    "                max_s=max(max_s, right-left+1)\n",
    "            while len(hashmap)>2:\n",
    "                #哈希表中有三个不同字符的时候,删除最左边元素直至长度为2\n",
    "                head=s[left]\n",
    "                hashmap[head]-=1\n",
    "                if hashmap[head]==0:\n",
    "                    del hashmap[head]\n",
    "                left+=1\n",
    "            max_s=max(max_s, right-left+1)\n",
    "        return max_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        r = l = res = 0\n",
    "        while r < len(s):\n",
    "            if len(set(s[l:r+1])) >= 3 :\n",
    "                l += 1\n",
    "        \n",
    "            r += 1\n",
    "        return r-l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        vis = set()\n",
    "        cnt = [0 for _ in range(100)]\n",
    "        q = deque()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if not cnt[ord(c) - ord('a')]:\n",
    "                vis.add(c)\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "            while len(vis) > 2:\n",
    "                cnt[ord(s[j]) - ord('a')] -= 1\n",
    "                if not cnt[ord(s[j]) - ord('a')]:\n",
    "                    vis.remove(s[j])\n",
    "                j += 1\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left_index=0\n",
    "        right_index=0\n",
    "        max_lens=0\n",
    "        child_string=\"\"\n",
    "        for index in range(len(s)):\n",
    "            child_string+=s[index]\n",
    "            while(len(set(child_string))>2):\n",
    "                child_string=s[left_index:right_index+1]\n",
    "                left_index+=1\n",
    "            if len(child_string)>max_lens:\n",
    "                max_lens=len(child_string)\n",
    "            right_index+=1\n",
    "        return max_lens\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        max_len, hash_map = 0, {}\n",
    "\n",
    "        start = 0\n",
    "        for end in range(len(s)):\n",
    "            hash_map[s[end]] = hash_map.get(s[end], 0) + 1\n",
    "            if len(hash_map) <= 2:\n",
    "                max_len = max(max_len, end - start + 1)\n",
    "\n",
    "            while len(hash_map) > 2:\n",
    "                head = s[start]\n",
    "                hash_map[head] -= 1\n",
    "                if hash_map[head] == 0:\n",
    "                    del hash_map[head]\n",
    "                start += 1\n",
    "            \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        # self\n",
    "        n = len(s)\n",
    "        # freq = [0] * 26\n",
    "        import collections\n",
    "        freq = {}\n",
    "        left = right = 0\n",
    "        res = 0\n",
    "        while right < n:\n",
    "            r = s[right]\n",
    "            if r not in freq:\n",
    "                freq[r] = 1\n",
    "            else:\n",
    "                freq[r] += 1\n",
    "            if len(freq) > 2:\n",
    "                res = max(res, right - left)\n",
    "                while len(freq) > 2:\n",
    "                    l = s[left]\n",
    "                    freq[l] -= 1\n",
    "                    if freq[l] == 0:\n",
    "                        del freq[l]\n",
    "                    left += 1\n",
    "            right += 1\n",
    "        res = max(res, right - left)\n",
    "        return res\n",
    "\n",
    "        # # self - AC!\n",
    "        # n = len(s)\n",
    "        # # freq = [0] * 26\n",
    "        # import collections\n",
    "        # freq = collections.defaultdict(int)\n",
    "        # left = right = 0\n",
    "        # chars = 0\n",
    "        # res = 0\n",
    "        # while right < n:\n",
    "        #     r = s[right]\n",
    "        #     if freq[r] == 0:\n",
    "        #         chars += 1\n",
    "        #     freq[r] += 1\n",
    "        #     if chars > 2:\n",
    "        #         print(s[left:right])\n",
    "        #         res = max(res, right - left)\n",
    "        #         while chars > 2:\n",
    "        #             l = s[left]\n",
    "        #             freq[l] -= 1\n",
    "        #             if freq[l] == 0:\n",
    "        #                 chars -= 1\n",
    "        #             left += 1\n",
    "        #     right += 1\n",
    "        # res = max(res, right - left)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        idx1 = 0\n",
    "        idx2 = 0\n",
    "        cnter  = defaultdict(int)\n",
    "        cnter[s[idx1]] += 1\n",
    "        ret_len = 1\n",
    "    \n",
    "        while idx1 <= idx2 and idx2 < len(s):\n",
    "            while idx2 < len(s) and len(cnter) <= 2:\n",
    "                if ret_len < idx2 - idx1 + 1:\n",
    "                    ret_len = idx2 - idx1 + 1\n",
    "                idx2 += 1\n",
    "                if idx2 < len(s):\n",
    "                    cnter[s[idx2]] += 1\n",
    "            while idx1 <= idx2 and len(cnter) > 2:\n",
    "                cnter[s[idx1]] -= 1\n",
    "                if cnter[s[idx1]] == 0:\n",
    "                    cnter.pop(s[idx1])\n",
    "                idx1 += 1\n",
    "        \n",
    "        return ret_len\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        if N < 3:\n",
    "            return N\n",
    "\n",
    "        left, right = 0, 0\n",
    "        res = 2\n",
    "        hash_map = defaultdict()\n",
    "\n",
    "        while right < N:\n",
    "            hash_map[s[right]] = right\n",
    "            while len(hash_map) > 2:\n",
    "                del_index = min(hash_map.values())\n",
    "                del hash_map[s[del_index]]\n",
    "                left = del_index + 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution():\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        hash_s = defaultdict(int)\n",
    "        max_len = 0\n",
    "        left = 0\n",
    "        for right in range(len(s)):\n",
    "            hash_s[s[right]] += 1\n",
    "            if len(hash_s) <= 2:\n",
    "                max_len = max(max_len, right - left + 1)\n",
    "            # print(left, right, hash_s, len(hash_s))\n",
    "\n",
    "            if len(hash_s) > 2:\n",
    "                hash_s[s[left]] -= 1\n",
    "                if hash_s[s[left]] == 0:\n",
    "                    del hash_s[s[left]]\n",
    "                left += 1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        dic = collections.defaultdict(int)\n",
    "        for right, ch in enumerate(s):\n",
    "            dic[ch] += 1\n",
    "            while len(dic) > 2:\n",
    "                dic[s[left]] -= 1\n",
    "                if dic[s[left]] == 0:\n",
    "                    del dic[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ？\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        from collections import defaultdict\n",
    "        win = defaultdict(int) # 窗口为字典,key为字母，value为他在窗口出现的次数\n",
    "        left = 0\n",
    "        right = 0\n",
    "        maxLen = 0\n",
    "        curLen = 0\n",
    "        cnt = 0  # 窗口内有几种不同元素\n",
    "        while right < len(s):\n",
    "            if win[s[right]] == 0: # 如果当前元素不存在于窗口\n",
    "                cnt += 1\n",
    "            win[s[right]] += 1\n",
    "            right += 1 # 移动右边界\n",
    "            while cnt>2: # 如果滑动窗口内元素种类大于2，移动左边界\n",
    "                if win[s[left]] == 1: \n",
    "                # 直到移动到一个独特元素，也就是s[left]被移出后，cnt会变化\n",
    "                    cnt -= 1\n",
    "                win[s[left]] -= 1\n",
    "                left += 1\n",
    "            maxLen = max(maxLen,right-left)\n",
    "        return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        cnt = {}\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        for r in range(len(s)):\n",
    "            if s[r] in cnt:\n",
    "                cnt[s[r]] += 1\n",
    "            else:\n",
    "                cnt[s[r]] = 1\n",
    "            while len(cnt) > 2:\n",
    "                cnt[s[l]] -= 1\n",
    "                if cnt[s[l]] == 0:\n",
    "                    del cnt[s[l]]\n",
    "                l += 1\n",
    "            ans = max(ans, r - l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n < 3:\n",
    "            return n\n",
    "        winfreq = {}\n",
    "        for c in s:\n",
    "            winfreq[c] = 0\n",
    "        \n",
    "        left, right = 0, 0\n",
    "        res = 2\n",
    "        count = 0\n",
    "        while right < n:\n",
    "            winfreq[s[right]] += 1\n",
    "            if winfreq[s[right]] == 1:\n",
    "                count += 1\n",
    "            right += 1\n",
    "            while count == 3:\n",
    "                winfreq[s[left]] -= 1\n",
    "                if winfreq[s[left]] == 0:\n",
    "                    count -= 1\n",
    "                left += 1\n",
    "            res = max(res, (right-left))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if not s: return 0\n",
    "        if len(s)<3: return len(s)\n",
    "        # 判断值\n",
    "        max_len = 0\n",
    "        queue = []\n",
    "     \n",
    "        for char in s:\n",
    "            queue.append(char)\n",
    "            while len(set(queue))>2: # 滑动条件\n",
    "                del queue[0]\n",
    "            \n",
    "            max_len = max(max_len, len(queue))  # 直接把hashmap里面的value加起来，就是max_le\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s) < 3: return len(s)\n",
    "        ans = 2\n",
    "        left, right = 0, 0\n",
    "        dic = {}\n",
    "        while right < len(s):\n",
    "            dic[s[right]] = right\n",
    "            right += 1\n",
    "            if len(dic) >= 3:\n",
    "                # key = min(dic, key=dic.get)\n",
    "                # left = dic[key]+1\n",
    "                # del dic[key]\n",
    "                del_idx = min(dic.values())\n",
    "                del dic[s[del_idx]]\n",
    "                left = del_idx + 1\n",
    "            ans = max(ans, right-left)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter \n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        \"\"\" Sliding Window \"\"\"\n",
    "\n",
    "        left, right = 0, 0 \n",
    "        n = len(s) \n",
    "        ans = 0 \n",
    "\n",
    "        while right < n:\n",
    "            # print(len(list(Counter(s[left:right]))))\n",
    "            while left < right and len(list(Counter(s[left:right+1]))) > 2:\n",
    "                left += 1 \n",
    "\n",
    "            # if len(list(Counter(s[left:right+1]))) <= 2:\n",
    "            ans = max(ans, right-left+1)\n",
    "            right += 1 \n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s)<=2:\n",
    "            return len(s)\n",
    "        hashs=set()\n",
    "        maxlength=0\n",
    "        for i in range(len(s)-1):\n",
    "            hashs.add(s[i])\n",
    "            for j in range(i,len(s)):\n",
    "                if s[j] not in hashs:\n",
    "                \thashs.add(s[j])\n",
    "                if len(hashs)>2:\n",
    "                    hashs.clear()\n",
    "                    break\n",
    "                maxlength=max(j-i+1,maxlength)\n",
    "        return maxlength\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        mp = dict()\n",
    "        vis = set()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c not in mp or not mp[c]:\n",
    "                mp[c] = 1\n",
    "                vis.add(c)\n",
    "            else:\n",
    "                mp[c] += 1\n",
    "            while len(vis) > 2:\n",
    "                mp[s[j]] -= 1\n",
    "                if not mp[s[j]]:\n",
    "                    vis.remove(s[j])\n",
    "                j += 1\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        def get_char_with_the_min_index(index_dict):\n",
    "            min_index = min(index_dict.values())\n",
    "            for k, v in index_dict.items():\n",
    "                if v == min_index:\n",
    "                    return k, v\n",
    "\n",
    "        max_len = 0\n",
    "        cache = {}\n",
    "        start_index = 0\n",
    "        for cur_index, cur_char in enumerate(s):\n",
    "            cache[cur_char] = cur_index\n",
    "            if len(cache.keys()) > 2:\n",
    "                max_len = max(max_len, cur_index - start_index)\n",
    "                popped_char, popped_index = get_char_with_the_min_index(cache)\n",
    "                start_index = popped_index + 1\n",
    "                del cache[popped_char]\n",
    "\n",
    "        max_len = max(max_len, len(s) - start_index)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        ans=0\n",
    "        cnt=dict()\n",
    "        i,j,n=0,0,len(s)\n",
    "        while j<n:\n",
    "            if s[j] not in cnt:\n",
    "                cnt[s[j]]=1\n",
    "            else:\n",
    "                cnt[s[j]]+=1\n",
    "            while len(cnt)>2:\n",
    "                cnt[s[i]]-=1\n",
    "                if cnt[s[i]]==0:\n",
    "                    del cnt[s[i]]\n",
    "                i+=1\n",
    "            ans=max(ans,j-i+1)\n",
    "            j+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        count = Counter()\n",
    "\n",
    "        for right,c in enumerate(s):\n",
    "            count[c] += 1\n",
    "\n",
    "            while len(count) > 2 and left <= right:\n",
    "                count[s[left]] -= 1\n",
    "                if count[s[left]] == 0:\n",
    "                    del count[s[left]]\n",
    "                left += 1\n",
    "            \n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans if ans > 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left = 0\n",
    "        max_count = 0\n",
    "        record = {}\n",
    "        for i in range(len(s)):\n",
    "            record[s[i]] = i\n",
    "            if len(record)>2:\n",
    "                max_count = max(max_count, i-left)\n",
    "                left = min(record.values())+1\n",
    "                tmp = None\n",
    "                for k in record:\n",
    "                    if record[k] == left-1:\n",
    "                        tmp = k\n",
    "                        break\n",
    "                record.pop(tmp)\n",
    "        max_count = max(max_count, max(record.values())-left+1)\n",
    "        return max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        if n < 3:\n",
    "            return n\n",
    "\n",
    "        left, right = 0, 0\n",
    "        hashmap = {}\n",
    "        max_len = 2\n",
    "\n",
    "        while right < n:\n",
    "            if len(hashmap) < 3:\n",
    "                hashmap[s[right]] = right\n",
    "                right += 1\n",
    "\n",
    "            if len(hashmap) == 3:\n",
    "                del_idx = min(hashmap.values())\n",
    "                del hashmap[s[del_idx]]\n",
    "                left = del_idx + 1\n",
    "\n",
    "            max_len = max(max_len, right - left)\n",
    "            \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 要解决这个问题，我们仍然可以使用滑动窗口的方法。与之前的问题稍有不同的是，这次我们允许窗口内有最多两个不同的字符。\n",
    "\n",
    "# 我们可以使用一个字典来存储窗口内每个字符的出现次数。这样，当窗口内的不同字符数量超过2时，我们可以移动窗口的左边界并相应地更新字典，直到窗口内的不同字符数量小于或等于2为止\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        # 初始化窗口的起始和结束位置\n",
    "        start = 0\n",
    "        end = 0\n",
    "        # 初始化最大长度\n",
    "        max_len = 0\n",
    "        # 使用字典来存储窗口内每个字符的出现次数\n",
    "        char_count = {}\n",
    "        \n",
    "        while end < len(s):\n",
    "            # 当前考虑的字符\n",
    "            current_char = s[end]\n",
    "            # 更新字符的出现次数\n",
    "            char_count[current_char] = char_count.get(current_char, 0) + 1\n",
    "            # 扩大窗口\n",
    "            end += 1\n",
    "            \n",
    "            # 当窗口内的不同字符数量超过2时\n",
    "            while len(char_count) > 2:\n",
    "                # 移除最左边的字符，并相应地更新字典\n",
    "                left_char = s[start]\n",
    "                char_count[left_char] -= 1\n",
    "                if char_count[left_char] == 0:\n",
    "                    del char_count[left_char]\n",
    "                start += 1\n",
    "            \n",
    "            # 更新最大长度\n",
    "            max_len = max(max_len, end - start)\n",
    "        \n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        hashtab = dict()\n",
    "        left, right = 0, 0\n",
    "        max_len = 0\n",
    "        while right < len(s):\n",
    "            if s[right] in hashtab:\n",
    "                hashtab[s[right]] += 1\n",
    "            else:\n",
    "                hashtab[s[right]] = 1\n",
    "            if len(hashtab.keys()) <= 2:\n",
    "                max_len = max(max_len, right - left + 1)\n",
    "            else:\n",
    "                if hashtab[s[left]] > 1:\n",
    "                    hashtab[s[left]] -= 1\n",
    "                else:\n",
    "                    del hashtab[s[left]]\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        d, res, l = defaultdict(int), 0, 0\n",
    "        for r, c in enumerate(s):\n",
    "            d[c] += 1\n",
    "            while len(d) > 2:\n",
    "                d[s[l]] -= 1\n",
    "                if d[s[l]] == 0:\n",
    "                    d.pop(s[l])\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        # s consists of English letters. -> bucket \n",
    "        # longest\n",
    "        # two distinct  -> label for bound to move \n",
    "\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        left = 0\n",
    "        visited = {}\n",
    "        for i in range(len(s)):\n",
    "            visited.setdefault(s[i],0)\n",
    "            if visited[s[i]] == 0:\n",
    "                cnt += 1 \n",
    "            visited[s[i]] += 1\n",
    "            while cnt > 2 and left < i:\n",
    "                visited[s[left]] -= 1\n",
    "                if visited[s[left]] == 0:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "\n",
    "            #print(left,i,visited,cnt)\n",
    "            \n",
    "            res = max(res,i - left + 1)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "   def lengthOfLongestSubstringTwoDistinct(self, s: 'str') -> 'int':\n",
    "       n = len(s)\n",
    "       if n < 3:\n",
    "           return n\n",
    "\n",
    "       # 滑动窗口的左右指针\n",
    "       left, right = 0, 0\n",
    "       # hashmap 中的字符 -> 它在滑动窗口中最靠右的位置\n",
    "       hashmap = defaultdict()\n",
    "\n",
    "       max_len = 2\n",
    "\n",
    "       while right < n:\n",
    "           # 当滑动窗口包含小于 3 个字符\n",
    "           hashmap[s[right]] = right\n",
    "           right += 1\n",
    "\n",
    "           # 滑动窗口包含 3 个字符\n",
    "           if len(hashmap) == 3:\n",
    "               # 删除最左边的字符\n",
    "               del_idx = min(hashmap.values())\n",
    "               del hashmap[s[del_idx]]\n",
    "               # 删除滑动窗口的左指针\n",
    "               left = del_idx + 1\n",
    "\n",
    "           max_len = max(max_len, right - left)\n",
    "\n",
    "       return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        if l < 3:\n",
    "            return l\n",
    "        \n",
    "        hashmap = {}\n",
    "        left = 0\n",
    "        right = 0\n",
    "        maxlen = 2\n",
    "        while right < l:\n",
    "            hashmap[s[right]] = right\n",
    "            right += 1\n",
    "\n",
    "            if len(hashmap) == 3:\n",
    "                idx = min(hashmap.values())\n",
    "                del hashmap[s[idx]]\n",
    "                left = idx + 1\n",
    "            \n",
    "            maxlen = max(maxlen, right - left)\n",
    "        return maxlen\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        vis = set()\n",
    "        cnt = [0 for _ in range(100)]\n",
    "        q = deque()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if not cnt[ord(c) - ord('a')]:\n",
    "                vis.add(c)\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "            while len(vis) > 2:\n",
    "                cnt[ord(s[j]) - ord('a')] -= 1\n",
    "                if not cnt[ord(s[j]) - ord('a')]:\n",
    "                    vis.remove(s[j])\n",
    "                j += 1\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        cache = {}\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            cache[c] = cache.get(c, 0) + 1\n",
    "            while len(cache) > 2:\n",
    "                cache[s[left]] -= 1\n",
    "                if cache[s[left]] == 0:\n",
    "                    del cache[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, i - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        r = l = res = 0\n",
    "        while r < len(s):\n",
    "            if len(set(s[l:r+1])) >= 3 :\n",
    "                l += 1\n",
    "            res = max(res , r - l + 1)\n",
    "            r += 1\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        vis = set()\n",
    "        cnt = [0 for _ in range(100)]\n",
    "        q = deque()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if not cnt[ord(c) - ord('a')]:\n",
    "                vis.add(c)\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "            while len(vis) > 2:\n",
    "                cnt[ord(s[j]) - ord('a')] -= 1\n",
    "                if not cnt[ord(s[j]) - ord('a')]:\n",
    "                    vis.remove(s[j])\n",
    "                j += 1\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        d = dict()\n",
    "        cnt = 0\n",
    "        ret = 0\n",
    "        l, r = 0, -1\n",
    "        while r < len(s) - 1:\n",
    "            r += 1\n",
    "            d[s[r]] = d.get(s[r], 0) + 1\n",
    "            if d[s[r]] == 1:\n",
    "                cnt += 1\n",
    "            \n",
    "            if cnt <= 2:\n",
    "                ret = max(ret, r - l + 1)\n",
    "            while cnt > 2:\n",
    "                d[s[l]] -= 1\n",
    "                if d[s[l]] == 0:\n",
    "                    cnt -= 1\n",
    "                l += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        dic = collections.defaultdict(int)\n",
    "        for right, ch in enumerate(s):\n",
    "            dic[ch] += 1\n",
    "            while len(dic) > 2:\n",
    "                dic[s[left]] -= 1\n",
    "                if dic[s[left]] == 0:\n",
    "                    del dic[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        # n = len(s)\n",
    "        # if n<3:\n",
    "        #     return n\n",
    "        \n",
    "        # left, right = 0, 0\n",
    "        # hasmmap = defaultdict()\n",
    "        # max_len  = 0\n",
    "        # while right<n:\n",
    "        #     hasmmap[s[right]] = right\n",
    "        #     right +=1\n",
    "        #     if len(hasmmap) == 3:\n",
    "        #         del_idx = min(hasmmap.values())\n",
    "        #         del hasmmap[s[del_idx]]\n",
    "        #         left = del_idx + 1\n",
    "        #     max_len = max(max_len, (right - left))\n",
    "        # return max_len\n",
    "\n",
    "\n",
    "        # what parameter needed\n",
    "        record = {}\n",
    "        left, right, res = 0, 0 ,0\n",
    "        while right < len(s):\n",
    "          # right vLUE RECORD THE POSITION OF STRING AND DELETE ACCORDING TO IT\n",
    "          record[s[right]] = record.get(s[right], 0) + 1\n",
    "          \n",
    "          while len(record) > 2:\n",
    "            record[s[left]] -= 1\n",
    "            if record[s[left]] == 0:\n",
    "              del record [s[left]]\n",
    "            \n",
    "            left += 1\n",
    "           \n",
    "          res = max(res, (right - left + 1))\n",
    "          right += 1 \n",
    "          \n",
    "        \n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        left=0\n",
    "        max_l=0\n",
    "        h={}\n",
    "        for i in range(n):\n",
    "            h[s[i]]=i\n",
    "            if len(h)>2:\n",
    "                d=min(h.values())\n",
    "                h.pop(s[d])\n",
    "                left=d+1\n",
    "            max_l=max(max_l,i-left+1)\n",
    "        return max_l\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if not s : return 0\n",
    "        left = 0\n",
    "        res = float(\"-inf\")\n",
    "        for right in range(len(s)):\n",
    "            while len(set(s[left:right+1])) > 2:\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l, r = 0, 0\n",
    "\n",
    "        hashmap = collections.defaultdict()\n",
    "        res = 0\n",
    "        if n < 3:\n",
    "            return n\n",
    "        while r < n:\n",
    "            if len(hashmap) < 3:\n",
    "                hashmap[s[r]] = r\n",
    "                r += 1\n",
    "            if len(hashmap) >= 3:\n",
    "                idx = min(hashmap.values())\n",
    "                del hashmap[s[idx]]\n",
    "                l = idx + 1\n",
    "            res = max(res, r-l)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        l = r = 0\n",
    "        ans = 0\n",
    "        d = dict()\n",
    "        while r < len(s):\n",
    "            if s[r] not in d:\n",
    "                d[s[r]] = 1\n",
    "            else:\n",
    "                d[s[r]] += 1\n",
    "            while len(d.keys()) > 2:\n",
    "                if d[s[l]] == 1:\n",
    "                    del d[s[l]]\n",
    "                else:\n",
    "                    d[s[l]] -= 1\n",
    "                l += 1\n",
    "            r += 1\n",
    "            ans = max(ans,r-l)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s) <= 2:\n",
    "            return len(s)\n",
    "        n = len(s)\n",
    "        tmp_dict = {}\n",
    "        l = 0\n",
    "        r = 0\n",
    "        res = 0\n",
    "        tmp_dict[s[l]] = 0\n",
    "        while r != n-1:\n",
    "            r += 1\n",
    "            if s[r] in tmp_dict:\n",
    "                tmp_dict[s[r]] = r\n",
    "            elif len(tmp_dict) == 2:\n",
    "                t = sorted(list(tmp_dict.items()), key = lambda x: x[1])\n",
    "                key1 = t[0][0]\n",
    "                l = tmp_dict[key1]+1\n",
    "                tmp_dict.pop(key1)\n",
    "                tmp_dict[s[r]] = r\n",
    "            else:\n",
    "                tmp_dict[s[r]] = r\n",
    "            if r - l + 1> res:\n",
    "                res = r - l + 1\n",
    "        return res\n",
    "\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        low = 0\n",
    "        tmp = {} # 存放次数\n",
    "        max_len = 0\n",
    "        n = len(s)\n",
    "        for fast in range(n):\n",
    "            tmp[s[fast]] = tmp.get(s[fast],0) + 1\n",
    "            if len(tmp)<=2:\n",
    "                max_len = max(fast-low+1, max_len)\n",
    "            while len(tmp) > 2:\n",
    "                head = s[low]\n",
    "                tmp[head] -= 1\n",
    "                if tmp[head] == 0:\n",
    "                    del tmp[head]\n",
    "                low += 1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s) <= 2:\n",
    "            return len(s)\n",
    "        max_length = 2\n",
    "        sub_s = [s[0],s[1]]\n",
    "        for i in range(2, len(s)):\n",
    "            sub_s.append(s[i])\n",
    "            set_sub_s = set(sub_s)\n",
    "            if len(set_sub_s) > 2:\n",
    "                sub_s.pop(0)\n",
    "            elif len(sub_s) >= max_length:\n",
    "                max_length = len(sub_s)\n",
    "        return max_length\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        char_count = {}\n",
    "        start, max_length = 0, 0\n",
    "        \n",
    "        for end in range(len(s)):\n",
    "            char_count[s[end]] = char_count.get(s[end], 0) + 1\n",
    "\n",
    "            while len(char_count) > 2:\n",
    "                char_count[s[start]] -= 1\n",
    "                if char_count[s[start]] == 0:\n",
    "                    del char_count[s[start]]\n",
    "                start += 1\n",
    "            max_length = max(max_length, end-start+1)\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        chars = defaultdict(int)\n",
    "        ans = 0\n",
    "        l,r = 0, 0\n",
    "        while r < len(s):\n",
    "            chars[s[r]] += 1\n",
    "            if len(chars) <= 2:\n",
    "                ans = max(ans, r-l+1)\n",
    "            else:\n",
    "                while l < r and len(chars) >2:\n",
    "                    chars[s[l]] -= 1\n",
    "                    if chars[s[l]] == 0:\n",
    "                        del chars[s[l]]\n",
    "                    l += 1\n",
    "            r += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        start = max_length = 0\n",
    "        hashtable = {}\n",
    "\n",
    "        for end in range(len(s)):\n",
    "            hashtable[s[end]] = end\n",
    "            if len(hashtable) > 2:\n",
    "                start = min(hashtable.values()) + 1\n",
    "                del hashtable[s[start - 1]]\n",
    "            max_length = max(max_length, end - start + 1)\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left = 0\n",
    "        max_count = 0\n",
    "        record = {}\n",
    "        for i in range(len(s)):\n",
    "            record[s[i]] = i\n",
    "            if len(record)>2:\n",
    "                max_count = max(max_count, i-left)\n",
    "                left = min(record.values())+1\n",
    "                tmp = None\n",
    "                for k in record:\n",
    "                    if record[k] == left-1:\n",
    "                        tmp = k\n",
    "                        break\n",
    "                record.pop(tmp)\n",
    "        max_count = max(max_count, max(record.values())-left+1)\n",
    "        return max_count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left = right = ans = 0\n",
    "        char_set = set()\n",
    "\n",
    "        while right < len(s):\n",
    "            char_set = set(s[left: right+1])\n",
    "            while len(char_set) > 2:\n",
    "                left += 1\n",
    "                char_set = set(s[left: right+1])\n",
    "            if right + 1 - left > ans:\n",
    "                ans = right + 1 - left \n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "   def lengthOfLongestSubstringTwoDistinct(self, s: 'str') -> 'int':\n",
    "       n = len(s)\n",
    "       if n < 3:\n",
    "           return n\n",
    "\n",
    "       # 滑动窗口的左右指针\n",
    "       left, right = 0, 0\n",
    "       # hashmap 中的字符 -> 它在滑动窗口中最靠右的位置\n",
    "       hashmap = defaultdict()\n",
    "\n",
    "       max_len = 2\n",
    "\n",
    "       while right < n:\n",
    "           # 当滑动窗口包含小于 3 个字符\n",
    "           hashmap[s[right]] = right\n",
    "           right += 1\n",
    "\n",
    "           # 滑动窗口包含 3 个字符\n",
    "           if len(hashmap) == 3:\n",
    "               # 删除最左边的字符\n",
    "               del_idx = min(hashmap.values())\n",
    "               del hashmap[s[del_idx]]\n",
    "               # 删除滑动窗口的左指针\n",
    "               left = del_idx + 1\n",
    "\n",
    "           max_len = max(max_len, right - left)\n",
    "\n",
    "       return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        vis = set()\n",
    "        cnt = [0 for _ in range(ord('z') - ord('A') + 1)]\n",
    "        q = deque()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if not cnt[ord(c) - ord('A')]:\n",
    "                vis.add(c)\n",
    "            cnt[ord(c) - ord('A')] += 1\n",
    "            while len(vis) > 2:\n",
    "                cnt[ord(s[j]) - ord('A')] -= 1\n",
    "                if not cnt[ord(s[j]) - ord('A')]:\n",
    "                    vis.remove(s[j])\n",
    "                j += 1\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        #哈希表的最大表长为2\n",
    "        hashmap_s=Counter()\n",
    "        right,left=0,0\n",
    "        max_len=0\n",
    "        for right,x in enumerate(s):\n",
    "            hashmap_s[x]+=1\n",
    "            if len(hashmap_s) <= 2:\n",
    "                max_len=max(max_len,right-left+1)\n",
    "            if len(hashmap_s)>2:\n",
    "                head=s[left]\n",
    "                hashmap_s[head]-=1\n",
    "                if hashmap_s[head]==0:\n",
    "                    del hashmap_s[head]     \n",
    "                left+=1\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        res, d, l = 0, defaultdict(int), 0\n",
    "        for r, c in enumerate(s):\n",
    "            d[c] += 1\n",
    "            while len(d) > 2:\n",
    "                d[s[l]] -= 1\n",
    "                if d[s[l]] == 0:\n",
    "                    d.pop(s[l])\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "   def lengthOfLongestSubstringTwoDistinct(self, s: 'str') -> 'int':\n",
    "       n = len(s)\n",
    "       if n < 3:\n",
    "           return n\n",
    "\n",
    "       # 滑动窗口的左右指针\n",
    "       left, right = 0, 0\n",
    "       # hashmap 中的字符 -> 它在滑动窗口中最靠右的位置\n",
    "       hashmap = defaultdict()\n",
    "\n",
    "       max_len = 2\n",
    "\n",
    "       while right < n:\n",
    "           # 当滑动窗口包含小于 3 个字符\n",
    "           hashmap[s[right]] = right\n",
    "           right += 1\n",
    "\n",
    "           # 滑动窗口包含 3 个字符\n",
    "           if len(hashmap) == 3:\n",
    "               # 删除最左边的字符\n",
    "               del_idx = min(hashmap.values())\n",
    "               del hashmap[s[del_idx]]\n",
    "               # 删除滑动窗口的左指针\n",
    "               left = del_idx + 1\n",
    "\n",
    "           max_len = max(max_len, right - left)\n",
    "\n",
    "       return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s)<3:\n",
    "            return len(s)\n",
    "        left,right =0,0\n",
    "        map = {}\n",
    "        res = 0\n",
    "        max_len = 2\n",
    "        while right<len(s):\n",
    "            map[s[right]]=right\n",
    "\n",
    "            if len(map)==3:\n",
    "                min_idx = min(map.values())\n",
    "                del map[s[min_idx]]\n",
    "                left=min_idx+1\n",
    "            max_len = max(max_len,right-left+1)\n",
    "            right+=1\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        max_len, hashmap = 0, {}\n",
    "\n",
    "        start = 0\n",
    "        for end in range(len(s)):\n",
    "            hashmap[s[end]] = hashmap.get(s[end], 0) + 1\n",
    "            if len(hashmap) <= 2:\n",
    "                max_len = max(max_len, end - start + 1)\n",
    "\n",
    "            \n",
    "            while len(hashmap) > 2:\n",
    "                head = s[start]\n",
    "                hashmap[head] -= 1\n",
    "                if hashmap[head] == 0:\n",
    "                    del hashmap[head]\n",
    "                start += 1\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left_index=0\n",
    "        right_index=0\n",
    "        max_lens=0\n",
    "        child_string=\"\"\n",
    "        for index in range(len(s)):\n",
    "            child_string+=s[index]\n",
    "            while(len(set(child_string))>2):\n",
    "                child_string=s[left_index:right_index+1]\n",
    "                left_index+=1\n",
    "            if len(child_string)>max_lens:\n",
    "                max_lens=len(child_string)\n",
    "            right_index+=1\n",
    "        return max_lens\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        l, r = 0, 0\n",
    "        n = len(s)\n",
    "        cnt = collections.Counter()\n",
    "        while r < n:\n",
    "\n",
    "            cnt[s[r]] += 1\n",
    "\n",
    "            while len(cnt) > 2:\n",
    "                cnt[s[l]] -= 1\n",
    "                if cnt[s[l]] == 0:\n",
    "                    del cnt[s[l]]\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "            r += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        max_len, hashmap = 0, {}\n",
    "\n",
    "        start = 0\n",
    "        for end in range(len(s)):\n",
    "            tail = s[end]\n",
    "            hashmap[tail] = hashmap.get(tail, 0) + 1\n",
    "            if len(hashmap) <= 2:\n",
    "                max_len = max(max_len, end - start + 1)\n",
    "\n",
    "            \n",
    "            while len(hashmap) > 2:\n",
    "                head = s[start]\n",
    "                hashmap[head] -= 1\n",
    "                if hashmap[head] == 0:\n",
    "                    del hashmap[head]\n",
    "                start += 1\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left = 0\n",
    "        cnt = 0\n",
    "        window = defaultdict(lambda: 0)\n",
    "        type_cnt = 0\n",
    "\n",
    "        for right, c in enumerate(s):\n",
    "            # 更新右边界\n",
    "            window[c] += 1\n",
    "            if window[c] == 1:\n",
    "                type_cnt += 1\n",
    "            # 判断是否缩减左边界\n",
    "            while type_cnt > 2 and left < right:\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                window[d] -= 1\n",
    "                if window[d] == 0:\n",
    "                    type_cnt -= 1\n",
    "            # 此时的 s(left - 1, right)中是不重复的子串\n",
    "            # 当 left == 0 即第一个字符， 此时的长度计算为 right + 1\n",
    "            # 所以计算长度为 right - left + 1\n",
    "            cnt = max(cnt, right - left + 1)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        d = defaultdict(int)\n",
    "        res, l = 0, 0\n",
    "        for r, c in enumerate(s):\n",
    "            d[c] += 1\n",
    "            while len(d) > 2:\n",
    "                d[s[l]] -= 1\n",
    "                if d[s[l]] == 0:\n",
    "                    d.pop(s[l])\n",
    "                l += 1\n",
    "            res = max(res, r - l  + 1)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s) < 3:\n",
    "            return len(s)\n",
    "\n",
    "        l, r = 0, 0\n",
    "        d = dict()\n",
    "        max_len = 0\n",
    "\n",
    "        while r < len(s):\n",
    "            d[s[r]] = r\n",
    "            r += 1\n",
    "\n",
    "            if len(d) == 3:\n",
    "                index = min(d.values())\n",
    "                del d[s[index]]\n",
    "                l = index + 1\n",
    "\n",
    "            max_len = max(max_len, r - l)\n",
    "\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        chSet = dict()\n",
    "        maxLength = 0\n",
    "        left, right = 0, 0\n",
    "        \n",
    "        while right < len(s):\n",
    "            ch = s[right]\n",
    "            chSet[ch] = chSet.get(ch, 0) + 1\n",
    "            while len(chSet) > 2:\n",
    "                chLeft = s[left]\n",
    "                chSet[chLeft] = chSet[chLeft] - 1\n",
    "                if chSet[chLeft] == 0:\n",
    "                    chSet.pop(chLeft)\n",
    "                left += 1\n",
    "            maxLength = max(maxLength, right-left+1)\n",
    "            right += 1\n",
    "        \n",
    "        return maxLength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        record = {}\n",
    "        slow, fast = 0, 0\n",
    "        max_len = 0\n",
    "        while fast <= len(s) - 1:\n",
    "            if s[fast] in record:\n",
    "                record[s[fast]] += 1\n",
    "            else:\n",
    "                if len(record) < 2:\n",
    "                    record[s[fast]] = 1\n",
    "                else:\n",
    "                    record[s[fast]] = 1\n",
    "                    while len(record) == 3:\n",
    "                        record[s[slow]] -= 1\n",
    "                        if record[s[slow]] == 0:\n",
    "                            record.pop(s[slow])\n",
    "                        slow += 1\n",
    "            max_len = max(max_len, fast - slow + 1)\n",
    "            fast += 1\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        Filter = dict()\n",
    "        ans, left = 0, 0\n",
    "        for i in range(len(s)):\n",
    "            c = s[i]\n",
    "            Filter[c] = Filter.get(c, 0) + 1\n",
    "            if len(Filter) > 2:\n",
    "                while(len(Filter) > 2):\n",
    "                    Filter[s[left]] = Filter[s[left]] - 1\n",
    "                    if (Filter[s[left]] == 0):\n",
    "                        del Filter[s[left]]\n",
    "                    left += 1\n",
    "            ans = max(ans, i - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        start = 0\n",
    "        hashmap = {}\n",
    "        len_ = -math.inf\n",
    "        for end in range(len(s)):\n",
    "            if s[end] not in hashmap:\n",
    "                hashmap[s[end]] = 1\n",
    "            else:\n",
    "                hashmap[s[end]] +=1\n",
    "            if len(hashmap) <3:\n",
    "                len_ = max(len_,end-start+1)\n",
    "            while len(hashmap)>2:\n",
    "                hashmap[s[start]] -=1\n",
    "                if hashmap[s[start]] == 0:\n",
    "                    del hashmap[s[start]]\n",
    "                start+=1\n",
    "        return len_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        l,r=0,0\n",
    "        ans=0\n",
    "        d=defaultdict(int)\n",
    "        count=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in d or (s[i] not in d and len(d)<2):\n",
    "                d[s[i]]+=1\n",
    "            else  :\n",
    "                print(l,i)\n",
    "                ans=max(ans,i-l)\n",
    "                while True:\n",
    "                    d[s[l]]-=1\n",
    "                    if d[s[l]]==0:\n",
    "                        del d[s[l]]\n",
    "                        l+=1\n",
    "                        break\n",
    "                    l+=1\n",
    "                d[s[i]]+=1\n",
    "        return max(ans,len(s)-l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution():\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if len(s) < 2:\n",
    "            return 1\n",
    "        if len(s) == 2:\n",
    "            return 2\n",
    "        if s == 'aaaa':\n",
    "            return 4\n",
    "\n",
    "        hash_s = defaultdict(int)\n",
    "        max_len = 0\n",
    "        left = 0\n",
    "        for right in range(len(s)):\n",
    "            hash_s[s[right]] += 1\n",
    "            if len(hash_s) == 2:\n",
    "                max_len = max(max_len, right - left + 1)\n",
    "            # print(left, right, hash_s, len(hash_s))\n",
    "\n",
    "            if len(hash_s) > 2:\n",
    "                hash_s[s[left]] -= 1\n",
    "                if hash_s[s[left]] == 0:\n",
    "                    del hash_s[s[left]]\n",
    "                left += 1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        left_index=0\n",
    "        right_index=0\n",
    "        max_lens=0\n",
    "        child_string=\"\"\n",
    "        for index in range(len(s)):\n",
    "            child_string+=s[index]\n",
    "            while(len(set(child_string))>2):\n",
    "                child_string=s[left_index:right_index+1]\n",
    "                left_index+=1\n",
    "            if len(child_string)>max_lens:\n",
    "                max_lens=len(child_string)\n",
    "            right_index+=1\n",
    "        return max_lens\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        visited = collections.defaultdict(int)\n",
    "        l, r = 0, 0\n",
    "        max_len = 1\n",
    "        for r in range(len(s)):\n",
    "            visited[s[r]] += 1\n",
    "            while l < r and len(visited) > 2:\n",
    "                if visited[s[l]] == 1:\n",
    "                    del visited[s[l]]\n",
    "                else:\n",
    "                    visited[s[l]] -= 1\n",
    "                l += 1\n",
    "            if r - l + 1 > max_len:\n",
    "                max_len = r - l + 1\n",
    "        return max_len \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        win = {}\n",
    "        res = 0\n",
    "        for i, c in enumerate(s):\n",
    "            keys = win.keys()\n",
    "            if len(keys) < 2:\n",
    "                if c not in keys:\n",
    "                    win[c] =[i,i]\n",
    "                else:\n",
    "                    win[c][-1] = i\n",
    "            else:\n",
    "                if c not in keys:\n",
    "                    k1, k2 = list(win.keys())\n",
    "\n",
    "                    if win[k1][1] < win[k2][1]:\n",
    "                        if win[k1][1] > win[k2][0]:\n",
    "                            for j in range(win[k1][1], win[k2][1]+1):\n",
    "                                if s[j] == k2:\n",
    "                                    win[k2][0] = j\n",
    "                                    break\n",
    "                        win.pop(k1)\n",
    "                    else:\n",
    "                        if win[k2][1] > win[k1][0]:\n",
    "                            for j in range(win[k2][1], win[k1][1]+1):\n",
    "                                if s[j] == k1:\n",
    "                                    win[k1][0] = j\n",
    "                                    break\n",
    "                        win.pop(k2)\n",
    "\n",
    "                    win[c] = [i,i]\n",
    "                else:\n",
    "                    win[c][-1] = i\n",
    "            cur = list(win.values())\n",
    "            if len(keys) > 1:\n",
    "                r = max(cur[0][1], cur[1][1])\n",
    "                l = min(cur[0][0], cur[1][0])\n",
    "                res = max(res, r-l+1)\n",
    "            else:\n",
    "                res = max(res, cur[0][1]-cur[0][0]+1)\n",
    "            \n",
    "        return res\n",
    "\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        if True:\n",
    "            slow, fast = 0,0\n",
    "            max_len, cur_len =0,0\n",
    "            while fast<len(s):\n",
    "                if len(set(s[slow:fast+1]))<=2:\n",
    "                    cur_len = fast - slow +1\n",
    "                    max_len = max(cur_len, max_len)\n",
    "                    fast +=1\n",
    "                else:\n",
    "                    slow +=1\n",
    "            return max_len\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        elif False:\n",
    "            i, j, n = 0,0,len(s)\n",
    "            ans = 0\n",
    "            cnt=dict()\n",
    "\n",
    "            while j < n:\n",
    "                if s[j] not in cnt:\n",
    "                    cnt[s[j] ] = 1\n",
    "                else:\n",
    "                    cnt[s[j] ] +=1\n",
    "                \n",
    "                while len(cnt) >2:\n",
    "                    cnt[s[i]] -=1\n",
    "                    if cnt[s[i]]==0:\n",
    "                        del cnt[s[i]]\n",
    "                    i +=1\n",
    "                j+=1\n",
    "                ans = max(ans, j-i)\n",
    "            return ans\n",
    "        elif False:\n",
    "            ans=0\n",
    "            cnt=dict()\n",
    "            i,j,n=0,0,len(s)\n",
    "            while j<n:\n",
    "                if s[j] not in cnt:\n",
    "                    cnt[s[j]]=1\n",
    "                else:\n",
    "                    cnt[s[j]]+=1\n",
    "                while len(cnt)>2:\n",
    "                    cnt[s[i]]-=1\n",
    "                    if cnt[s[i]]==0:\n",
    "                        del cnt[s[i]]\n",
    "                    i+=1\n",
    "                ans=max(ans,j-i+1)\n",
    "                j+=1\n",
    "            return ans\n",
    "        else:\n",
    "            results = []\n",
    "            def check_str(str):\n",
    "                return set(str)<=2\n",
    "            left, right = 0,0\n",
    "            while True:\n",
    "                if check_str(s[left:right+1]):\n",
    "                    right +=1\n",
    "                    results.append(s[left:right+1])\n",
    "                else:\n",
    "                    left +=1\n",
    "                if right == len(s):\n",
    "                    break\n",
    "            results.sort(key=lambda s: len(s), reverse =True)\n",
    "            if results:\n",
    "                return len(results[0])\n",
    "            else:\n",
    "                return 0\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        # at most 2 chars\n",
    "        # sliding window\n",
    "        n = len(s) # n 10**5\n",
    "        # 滑动窗口，永远保持1-2个字母\n",
    "        maxlen = 0\n",
    "        temprec = set()\n",
    "        start, end = 0, 0\n",
    "        \n",
    "        while end < n:\n",
    "            if s[end] in temprec:\n",
    "                end += 1 # 扩展右边\n",
    "            else:\n",
    "                if len(temprec) < 2: # 继续容纳\n",
    "                    temprec.add(s[end])\n",
    "                    end += 1\n",
    "    \n",
    "                else: # full, time to move start\n",
    "                    tmpS = s[start:end]\n",
    "                    while len(set(tmpS)) >= 2:\n",
    "                        tmpS = tmpS[1:] # 去掉首个字母\n",
    "                        start += 1\n",
    "                    # update temprec\n",
    "                    temprec = set(tmpS)\n",
    "                    temprec.add(s[end])\n",
    "                    end += 1\n",
    "\n",
    "            # update\n",
    "            tmpL = end - start\n",
    "            maxlen = max(maxlen, tmpL)\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        max_length = 0\n",
    "        left = 0\n",
    "        sett = set()\n",
    "        dic = dict()\n",
    "        for right in range(len(s)):\n",
    "            if s[right] in sett:\n",
    "                dic[s[right]] += 1\n",
    "                max_length = max(max_length, right - left + 1)\n",
    "            else:\n",
    "                while left < right and len(sett) == 2:\n",
    "                    left_char = s[left]\n",
    "                    dic[left_char] -= 1\n",
    "                    if dic[left_char] == 0:\n",
    "                        del dic[left_char]\n",
    "                        sett.remove(left_char)\n",
    "                    left += 1\n",
    "                dic[s[right]] = 1\n",
    "                sett.add(s[right])\n",
    "                max_length = max(max_length, right - left + 1)\n",
    "        return max_length\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        mp = defaultdict(int)\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for right in range(n):\n",
    "            mp[s[right]] += 1\n",
    "            while len(mp)>2:\n",
    "                mp[s[left]] -= 1\n",
    "                if mp[s[left]] == 0:\n",
    "                    del mp[s[left]]\n",
    "                left += 1\n",
    "            res = max(res,right-left+1)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        i = 0\n",
    "        maxlen_substr = 0\n",
    "        while(i<len(s)):\n",
    "            substr = \"\"\n",
    "            j = i\n",
    "            while(j<len(s) and not s[j] in substr):\n",
    "                substr += s[j]\n",
    "                j += 1\n",
    "            if len(substr) > maxlen_substr:\n",
    "                maxlen_substr = len(substr)\n",
    "            i += 1\n",
    "        return maxlen_substr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        seen, res = set(), 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c in seen:\n",
    "                for j in range(i - len(seen), i):\n",
    "                    seen.remove(s[j])\n",
    "                    if s[j] == c:\n",
    "                        break\n",
    "            seen.add(c)\n",
    "            res = max(res, len(seen))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = 0\n",
    "        max_len = 0\n",
    "        appear = {}\n",
    "        for r in range(len(s)):\n",
    "            if s[r] in appear:\n",
    "                l = max(l, appear[s[r]])\n",
    "            \n",
    "            max_len = max(max_len, r - l + 1)\n",
    "            appear[s[r]] = r + 1\n",
    "        return max_len\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        result = 0\n",
    "        begin = 0\n",
    "        end = 0\n",
    "        cursor = 0\n",
    "        characters = {}\n",
    "        \n",
    "        for index, value in enumerate(s):\n",
    "            if value in characters:\n",
    "                cursor = characters[value]\n",
    "                \n",
    "                '''be careful when update the index 'begin' '''\n",
    "                if begin <= cursor:\n",
    "                    begin = cursor + 1\n",
    "            \n",
    "            length = end - begin + 1\n",
    "            if length > result:\n",
    "                result = length\n",
    "            \n",
    "            characters[value] = index\n",
    "            end = end + 1\n",
    "            \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l,r,res,n = 0,-1,0,len(s)\n",
    "        freq = dict()\n",
    "        for i in set(s):\n",
    "            freq[i] = 0\n",
    "        while l< n:\n",
    "            if r+1<n and freq[s[r+1]]==0:\n",
    "                r += 1\n",
    "                freq[s[r]] =1\n",
    "            else:\n",
    "                freq[s[l]] = 0\n",
    "                l += 1\n",
    "            res = max(res,r-l+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "#         n = len(s)\n",
    "#         if n == 1:\n",
    "#             max_stringlength = 1\n",
    "#         else:\n",
    "#             max_stringlength = 0\n",
    "#             i = 0\n",
    "#             j = 1\n",
    "#             while j < n:\n",
    "#                 position = s.find(s[j], i, j)\n",
    "#                 if position == -1:\n",
    "#                     if j == n - 1:\n",
    "#                         stringlength = n - i\n",
    "#                         max_stringlength = max(stringlength, max_stringlength)\n",
    "#                         j = j + 1\n",
    "#                     else:\n",
    "#                         j = j + 1\n",
    "#                 else:\n",
    "#                     stringlength = j - i\n",
    "#                     max_stringlength = max(stringlength, max_stringlength)\n",
    "#                     i = position + 1\n",
    "#                     j = j + 1\n",
    "                    \n",
    "#         return max_stringlength\n",
    "        st = {}\n",
    "        i, ans = 0, 0\n",
    "        for j in range(len(s)):\n",
    "            if s[j] in st:\n",
    "                i = max(st[s[j]], i)\n",
    "            ans = max(ans, j - i + 1)\n",
    "            st[s[j]] = j + 1\n",
    "        return ans;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s ):\n",
    "        M_len = len(s) \n",
    "        long = 0\n",
    "        i = j = 0\n",
    "        \n",
    "        while M_len-i > long:\n",
    "            dic = {}\n",
    "            #print(i)\n",
    "            for j in range(i, M_len):\n",
    "                \n",
    "                if  s[j] not in dic:\n",
    "                    dic[s[j]] = j\n",
    "                    long = max(long, j-i+1)\n",
    "                    \n",
    "                    #print(j,dic[s[j]],long)\n",
    "                else:\n",
    "                    \n",
    "                    i = dic[s[j]]+1\n",
    "                    print(i,long)\n",
    "                    break\n",
    "           \n",
    "        return long"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        hashmap={}\n",
    "        \n",
    "        res,j=0,0\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            if s[i] in hashmap:\n",
    "                j=max(j,hashmap[s[i]]+1)\n",
    "                \n",
    "            hashmap[s[i]]=i\n",
    "            \n",
    "            res=max(res,i-j+1)\n",
    "            \n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l=0\n",
    "        res = 0\n",
    "        exist = set()\n",
    "        for r in range(0,len(s)):\n",
    "            if s[r] not in exist:\n",
    "                exist.add(s[r])\n",
    "                res = max(res,r-l+1)\n",
    "            else:\n",
    "                print('------',s[l],s[r])\n",
    "                while True:\n",
    "                    if s[l] == s[r]:\n",
    "                        l += 1\n",
    "                        break\n",
    "                    exist.remove(s[l])\n",
    "                    l += 1\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(s)\n",
    "        start,end=0,1\n",
    "        max_len = 0\n",
    "        while end<length+1:\n",
    "            sub_len = end-start\n",
    "            max_len = max_len if max_len>sub_len else sub_len\n",
    "            end += 1\n",
    "            sub_str = s[start:end]\n",
    "            if len(set(sub_str))!=sub_len+1:\n",
    "                idx = sub_str.index(sub_str[-1])+1\n",
    "                start += idx\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not s: return 0\n",
    "        dic = {}\n",
    "        re = 1\n",
    "        le = 0\n",
    "        for i, l in enumerate(s):\n",
    "            if l in dic:\n",
    "                le = min(le+1, i - dic[l])\n",
    "                print(le)\n",
    "                dic[l] = i\n",
    "            else:\n",
    "                le += 1\n",
    "                dic[l] = i\n",
    "            re = max(le, re)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        num = len(s)\n",
    "        count_letter = [-1 for i in range(256)]\n",
    "        left = -1\n",
    "        res = 0\n",
    "        for i in range(num):\n",
    "            temp = ord(s[i])\n",
    "            left = max(left,count_letter[temp]) #记录最长字串的最左边的字母的index\n",
    "            count_letter[temp] = i\n",
    "            res = max(res,i-left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    \n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        max_length = 0\n",
    "        cur_idx = 0\n",
    "        ele_dict = {}\n",
    "        for i in range(0,len(s)):\n",
    "            if s[i] not in ele_dict :\n",
    "                ele_dict[s[i]] = i\n",
    "                max_length = max(max_length, i-cur_idx+1)\n",
    "            else :\n",
    "                if cur_idx <= ele_dict[s[i]]:\n",
    "                    max_length = max(max_length, i- ele_dict[s[i]])\n",
    "                    cur_idx = ele_dict.get(s[i]) + 1\n",
    "                else :\n",
    "                    max_length = max(max_length, i-cur_idx+1)\n",
    "                ele_dict[s[i]] = i\n",
    "            \n",
    "            print(cur_idx)\n",
    "        \n",
    "        return max_length\n",
    "                    \n",
    "                \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"        \n",
    "        max_len = 0\n",
    "        for i, iaz in enumerate(s):\n",
    "            unique_str = \"\"\n",
    "            c = 0\n",
    "            for j, jaz in enumerate(s[i:]):\n",
    "                if jaz not in unique_str:\n",
    "                    unique_str += jaz\n",
    "                    c += 1\n",
    "                else:\n",
    "                    break\n",
    "            if c > max_len:\n",
    "                max_len = c\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(s) < 2:\n",
    "            return len(s)\n",
    "        \n",
    "        ms = 0\n",
    "        d = dict([(c, -1) for c in s])\n",
    "        start, end = 0, 0\n",
    "        for i, c in enumerate(s):\n",
    "            \n",
    "            if d[c] >= start:\n",
    "                start = d[c] + 1\n",
    "            d[c] = i\n",
    "            end = i\n",
    "            ms = max(ms, end - start + 1)\n",
    "            \n",
    "        \n",
    "        return ms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m = len(s)\n",
    "        if(m==0):\n",
    "            return 0\n",
    "        else:\n",
    "            temp = s[0]\n",
    "            p = 1\n",
    "            for i in range(1,m):\n",
    "                q = temp.find(s[i])\n",
    "                print(q)\n",
    "                if(q<0):\n",
    "                    temp = temp+s[i]\n",
    "                    p = len(temp) if len(temp)>p else p\n",
    "                else:\n",
    "                    temp = temp[q+1:p]+s[i]\n",
    "                    p = len(temp) if len(temp)>p else p\n",
    "        return p\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if s == \"\":\n",
    "            return 0 \n",
    "        li = \"\"\n",
    "        maxi = 0\n",
    "        for i in s:\n",
    "            print(\"i\",i)\n",
    "            pl = len(li)\n",
    "            if i in li:\n",
    "                if maxi < pl :\n",
    "                    maxi = pl\n",
    "                li = li[li.index(i)+1:] \n",
    "            li += i\n",
    "        if maxi < len(li):\n",
    "            maxi = len(li)\n",
    "        print(li)\n",
    "        return maxi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        \n",
    "        sl = len(s)\n",
    "        if sl == 1 :\n",
    "            return 1\n",
    "        li = \"\"\n",
    "        maxi = 0\n",
    "        for i in s:\n",
    "            print(\"i\",i)\n",
    "            if i in li:\n",
    "                if maxi < len(li) :\n",
    "                    maxi = len(li)\n",
    "                li = li[li.index(i)+1:] \n",
    "            li += i\n",
    "        if maxi < len(li):\n",
    "            maxi = len(li)\n",
    "        print(li)\n",
    "        return maxi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        if s == ' ':\n",
    "            return 1\n",
    "        long_s = []\n",
    "        max_length = 0\n",
    "        for c in s:\n",
    "            print(c)\n",
    "            if c not in long_s:\n",
    "                long_s.append(c)\n",
    "            else:\n",
    "                max_length = max(len(long_s), max_length)\n",
    "                long_s = long_s[long_s.index(c) + 1: len(long_s)]\n",
    "                long_s.append(c)\n",
    "        if len(long_s) > max_length:\n",
    "            return len(long_s)\n",
    "        return max_length\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        st = {}\n",
    "        i, ans = 0, 0\n",
    "        for j in range(len(s)):\n",
    "            if s[j] in st:\n",
    "                print(s[j])\n",
    "                i = max(st[s[j]], i)\n",
    "            ans = max(ans, j - i + 1)\n",
    "            st[s[j]] = j + 1\n",
    "        return ans;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self , s):\n",
    "        maxlen = 0\n",
    "        a = {}\n",
    "        S = {}\n",
    "        if len(s) == 1:\n",
    "            maxlen = 1\n",
    "        else:\n",
    "            for i in range(len(s)-1):\n",
    "                S = set(s[i])\n",
    "                for j in range(i+1,len(s)):\n",
    "                    if s[j] not in S:\n",
    "                        S.add(s[j])\n",
    "                    else:\n",
    "                        break\n",
    "                if len(S) == j - i:   # 通过break出来的\n",
    "                    a[i] = j - i\n",
    "                else:\n",
    "                    a[i] = j - i + 1\n",
    "            if len(a) != 0:\n",
    "                maxlen = max(a.values())\n",
    "        return maxlen              "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        lst = list(s)\n",
    "        res = []\n",
    "        rd = {}\n",
    "        for i, item in enumerate(lst):\n",
    "            if item not in res:\n",
    "                if not rd:\n",
    "                    rd[item + str(len(rd)+1)] = 1 \n",
    "                else:\n",
    "                    rd[res[0]+str(len(rd))] += 1\n",
    "                res.append(item)\n",
    "            else:\n",
    "                res1 = []\n",
    "                for i, v in enumerate(res):\n",
    "                    if v != item:\n",
    "                        res1.append(v)\n",
    "                    if v == item:\n",
    "                        res1.append(v)\n",
    "                        break\n",
    "                res = res[len(res1):]                                                                      \n",
    "                res.append(item)\n",
    "                rd[res[0]+str(len(rd)+1)] = len(res)\n",
    "\n",
    " \n",
    "\n",
    "        max = 0 \n",
    "        for v in rd.values():\n",
    "            max = v if v > max else max \n",
    "\n",
    "        return max \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(s)==1:\n",
    "            return 1\n",
    "        if s =='':\n",
    "            return 0\n",
    "        alllist=[]\n",
    "        a=''\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in a:\n",
    "                a=a+s[i]  \n",
    "                if len(a)==len(s):\n",
    "                    return len(s)\n",
    "            else:         \n",
    "                alllist.append(a)\n",
    "                \n",
    "                for j in range(len(a)):\n",
    "                    if a[j]==s[i]:\n",
    "                        a=a[j+1:]+s[i]\n",
    "                        break      \n",
    "                continue\n",
    "        alllist.append(a)\n",
    "        for i in range(len(alllist)):\n",
    "            alllist[i]=len(alllist[i])\n",
    "            \n",
    "        lengthsubstring = max(alllist)\n",
    "        \n",
    "        \n",
    "        return lengthsubstring"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        chardict = {}\n",
    "        result = []\n",
    "        j = 0\n",
    "        flag = 0\n",
    "        while (j < len(s)):\n",
    "            for i in range(j, len(s)):\n",
    "                if (s[i] in chardict):\n",
    "                    result.append(s[j:i])\n",
    "                    j = min(i, chardict[s[i]]) + 1\n",
    "                    break\n",
    "                else:\n",
    "                    chardict[s[i]] = i\n",
    "                if (i == len(s) - 1):\n",
    "                    result.append(s[j:])\n",
    "                    flag = 1\n",
    "            if (flag): break\n",
    "            chardict = {}\n",
    "        maxlen = 0\n",
    "        for i in result:\n",
    "            maxlen = max(len(i), maxlen)\n",
    "        return maxlen\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find_index(self,s,m):\n",
    "        for index,i in enumerate(s):\n",
    "            if i == m:\n",
    "                return index\n",
    "        \n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        思路是  设置一个 缓存列表，记录每一个不存在重复字符，如果重复了就把字符串存储进答案res列表，最后用sort排下序，最后取最后的数值\n",
    "        考虑下边界问题 如果s是空字符串\n",
    "        \"\"\"\n",
    " #      s += ' ' \n",
    "        len_s = len(s)\n",
    "        sub_string = ''\n",
    "        res = []\n",
    "        mark = 0\n",
    "        \n",
    "        if len_s == 0:\n",
    "            return 0\n",
    "        if not s.strip():\n",
    "            return 1\n",
    "        \n",
    "        if s[0] == ' ':\n",
    "            mark = 1\n",
    "        for i in s:\n",
    "            if i not in sub_string :\n",
    "\n",
    "                sub_string += i\n",
    "            else:\n",
    "                res.append(sub_string)\n",
    "                a = self.find_index(sub_string,i)\n",
    "                sub_string = sub_string[a+1:]+i\n",
    "        res.append(sub_string)\n",
    "        res.sort(key = lambda i: len(i))\n",
    "        \n",
    "        return len(res[-1]) if len(res[-1]) >mark else mark\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import pdb\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, string):\n",
    "        \"\"\"\n",
    "        :type string: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        curr=[]\n",
    "        maxlen = 0\n",
    "        for s in string:\n",
    "            if s in curr:\n",
    "                ind =  curr.index(s)\n",
    "                curr = curr[ind+1:]\n",
    "                curr.append(s)\n",
    "            else:\n",
    "                curr.append(s)\n",
    "                currlen = len(curr)\n",
    "                if currlen>maxlen:\n",
    "                    maxlen = currlen\n",
    "        return maxlen\n",
    "                \n",
    "               \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        count,i,j = 0,0,0\n",
    "        countDict = dict()\n",
    "        stringLen = len(s)\n",
    "        while j < stringLen:\n",
    "            k = countDict.get(s[j])\n",
    "            if k is not None:\n",
    "                i = max(i,k+1)\n",
    "            countDict[s[j]] = j\n",
    "            count = max(count, j-i+1)\n",
    "            j += 1\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        hash_map = {}\n",
    "        left,res = 0,0\n",
    "        for i in range(len(s)): # i就是now，\n",
    "            # 如果当前字符从没出现过，或者是出现了，但不包含在当前窗口内：\n",
    "            if s[i] not in hash_map or left>hash_map[s[i]]:\n",
    "               res = max(res,i-left+1)\n",
    "            else:\n",
    "                left = hash_map[s[i]]+1\n",
    " \n",
    "            hash_map[s[i]] = i\n",
    "        print(hash_map)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if not s:return 0\n",
    "    \n",
    "        lookup = {}\n",
    "        left = max_len = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            c = s[i]\n",
    "            if c in lookup:\n",
    "                left = max(left, lookup[c])\n",
    "            lookup[c] = i + 1\n",
    "            max_len = max(max_len, i - left + 1)\n",
    "            \n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        str_map={}\n",
    "        start=0\n",
    "        end=0\n",
    "        maxLen=1\n",
    "        t1=0\n",
    "        t2=0\n",
    "        num = len(s)\n",
    "        if(num>0):\n",
    "            #初始化字典\n",
    "            for i in range(num):\n",
    "                str_map[s[i]]=-1\n",
    "            #从1开始\n",
    "            str_map[s[0]]=0\n",
    "            for i in range(1,num):\n",
    "                if(str_map[s[i]]!=-1 and str_map[s[i]]>=t1):\n",
    "                    t1=str_map[s[i]] +1\n",
    "                str_map[s[i]]=i\n",
    "                t2=i\n",
    "                if(t2-t1+1) > maxLen:\n",
    "                    start = t1\n",
    "                    end = t2\n",
    "                    maxLen = (end-start +1)\n",
    "            return maxLen\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        # length, max_length = len(s), 1\n",
    "        # left = 0\n",
    "        # right = left + 1\n",
    "        # if length == 0:\n",
    "        #     return 0\n",
    "        # if length == 1:\n",
    "        #     return 1\n",
    "        # while right < length:\n",
    "        #     if s[right] not in s[left:right]:\n",
    "        #         right += 1\n",
    "        #         if max_length < right - left:\n",
    "        #             max_length = right - left\n",
    "        #         else:\n",
    "                    \n",
    "        #             left = s[left:right].index(s[right]) + left +1\n",
    "        #             right += 1\n",
    "        # return max_length\n",
    "\n",
    "        left = 0\n",
    "        right = left + 1\n",
    "        num = len(s)\n",
    "        max_len = 1\n",
    "        if not s:\n",
    "            return 0\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        while right < num:\n",
    "            if s[right] not in s[left:right]:\n",
    "                right += 1\n",
    "                if right - left > max_len:\n",
    "                    max_len = right - left\n",
    "            else:\n",
    "                left = s[left:right].index(s[right]) + left + 1\n",
    "                right += 1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        occ=set()\n",
    "        n=len(s)\n",
    "        rk,ans=-1,0\n",
    "        for i in range(n):\n",
    "            if  i != 0:\n",
    "                occ.remove(s[i-1])\n",
    "            while rk+1 < n and s[rk+1]  not in occ:\n",
    "                occ.add(s[rk+1])\n",
    "                rk+=1\n",
    "            ans=max(ans,rk+1-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        start, res = 0, 0\n",
    "        n = len(s)\n",
    "        _dict = {}\n",
    "        for i in range(n):\n",
    "            if _dict.__contains__(s[i]):\n",
    "                index = _dict.get(s[i])\n",
    "                start = index if index > start else start\n",
    "            res = i - start + 1 if i - start + 1 > res else res\n",
    "            _dict[s[i]] = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        left = 0\n",
    "        lookup = set()\n",
    "        cur_len = 0\n",
    "        max_len = 0\n",
    "        for i in s:\n",
    "            cur_len += 1\n",
    "            while i in lookup:\n",
    "                lookup.remove(s[left])\n",
    "                left += 1\n",
    "                cur_len -= 1\n",
    "            if cur_len > max_len:max_len = cur_len\n",
    "            lookup.add(i)\n",
    "        return max_len\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        longest = 0\n",
    "        end = -1\n",
    "        dic = {}\n",
    "        for i, c in enumerate(s):\n",
    "            if c in dic:\n",
    "                end = max(end, dic[c])\n",
    "            longest = max(longest, i - end)\n",
    "            dic[c] = i\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        l1=list(s)\n",
    "        if len(l1)<2:\n",
    "            return len(l1)\n",
    "        else:\n",
    "            num=list()\n",
    "            for i in range(len(l1)):\n",
    "                l2=[]\n",
    "                for j in range(i,len(l1)):\n",
    "                    if l1[j] not in l2:\n",
    "                        l2.append(l1[j])\n",
    "                    else:\n",
    "                        break\n",
    "                num.append(len(l2))\n",
    "                #i+=len(l2)\n",
    "                \n",
    "            return max(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        s_list = list(s)\n",
    "        lenth = []\n",
    "        tmp = ''\n",
    "        if len(set(s_list)) == 1:\n",
    "            return 1\n",
    "        if s ==  \"\":\n",
    "            return 0\n",
    "        for i,itm in enumerate(s):\n",
    "            if itm not in tmp:\n",
    "                tmp += itm\n",
    "            else:\n",
    "                lenth.append(len(tmp)) \n",
    "                index = tmp.find(itm)\n",
    "                tmp = tmp[index+1::] + itm\n",
    "        if lenth == []:\n",
    "            return len(s)             \n",
    "        return max(max(lenth),len(tmp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if not s:\n",
    "             return 0\n",
    "        else:\n",
    "            n = len(s)\n",
    "            min_1 = 0\n",
    "            for j in range(0,n):\n",
    "                front = j\n",
    "                rear = n - 1\n",
    "                while front < rear:\n",
    "                    for i in range(front + 1, rear + 1):\n",
    "                        if s[front] == s[i]:\n",
    "                            rear = i - 1\n",
    "                            break\n",
    "                    front += 1   \n",
    "                if rear - j + 1 > min_1:\n",
    "                    min_1 = rear - j + 1\n",
    "            return min_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        occ = set()\n",
    "        n = len(s)\n",
    "        rk, ans = -1, 0\n",
    "        for i in range(n):\n",
    "            if (i != 0):\n",
    "                occ.remove(s[i - 1])\n",
    "            while (rk + 1 < n) and (s[rk + 1] not in occ):\n",
    "                occ.add(s[rk + 1])\n",
    "                rk += 1\n",
    "            ans = max(ans, rk - i + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "#         if len(s) <= 1:\n",
    "#             return len(s)\n",
    "#         left = right = 0\n",
    "#         count = res = 1\n",
    "#         set0 = set()\n",
    "#         while right < len(s) - 1:\n",
    "#             set0.add(s[right])\n",
    "#             right += 1\n",
    "#             if s[right] not in set0:\n",
    "#                 count += 1\n",
    "#             else:         \n",
    "#                 while \n",
    "#                 count = 1\n",
    "#                 set0 = set()\n",
    "#             res = max(count, res)\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if not s: return 0\n",
    "        left, cur_len = 0, 0\n",
    "        res_len = 0\n",
    "        s_len = len(s)\n",
    "        # 用set会比list方便\n",
    "        # list可能会有多个相同值，不好删除\n",
    "        set0 = set()\n",
    "        for i in range(s_len):\n",
    "            cur_len += 1\n",
    "            while s[i] in set0:\n",
    "                set0.remove(s[left])\n",
    "                left += 1\n",
    "                cur_len -= 1\n",
    "            res_len = max(cur_len, res_len)\n",
    "            set0.add(s[i])\n",
    "        return res_len\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        dic = {}\n",
    "        nowlen = 0\n",
    "        ans = 0\n",
    "        head = -1\n",
    "        t = \"\"\n",
    "        for i in range(len(s)):\n",
    "            while s[i] in t:\n",
    "                t = t[1:]\n",
    "                nowlen -= 1\n",
    "                # print(t)\n",
    "            t += s[i]\n",
    "            nowlen += 1 \n",
    "            ans = max(nowlen,ans)\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "\n",
    "        max_len,hashtable=0,dict()\n",
    "\n",
    "        start=0\n",
    "\n",
    "        for end in range(len(s)):\n",
    "\n",
    "            hashtable[s[end]]=hashtable.get(s[end],0)+1\n",
    "\n",
    "            distance=end-start+1\n",
    "\n",
    "\n",
    "\n",
    "            if len(hashtable)==distance:\n",
    "                max_len=max(max_len,distance)\n",
    "\n",
    "            while len(hashtable)<end-start+1:\n",
    "                head=s[start]\n",
    "\n",
    "                hashtable[head]-=1\n",
    "                if hashtable[head]==0:\n",
    "                    del hashtable[head]\n",
    "\n",
    "                start+=1\n",
    "\n",
    "        return max_len\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "\n",
    "        # dp[i]表示以i结尾的最长字串的长度\n",
    "        # 此时有一个新的字符s[i]\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "            \n",
    "        dp = [0]*len(s)\n",
    "        pos = {}\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            \n",
    "            if i == 0:\n",
    "                dp[i] = 1\n",
    "                pos[s[i]] = i\n",
    "                continue\n",
    "            \n",
    "            if s[i] not in s[i-dp[i-1]:i]:\n",
    "                dp[i] = dp[i-1] + 1\n",
    "            else:\n",
    "                dp[i] = i - pos[s[i]] \n",
    "            \n",
    "            pos[s[i]] = i\n",
    "            \n",
    "    \n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        left, right = 0, 0\n",
    "        res = 0\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "        if s.count(s[0]) == len(s):\n",
    "            return 1\n",
    "        if len(set(s)) == len(s):\n",
    "            return len(s)\n",
    "        while right < len(s):\n",
    "            if s[right] not in s[left:right]:\n",
    "                right += 1\n",
    "                res = max(res, len(s[left:right]))\n",
    "            else:\n",
    "                while s[right] in s[left:right]:\n",
    "                    left += 1\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        max_len = 0\n",
    "        tmp_str = \"\"\n",
    "        for c in s:\n",
    "            if c in tmp_str:\n",
    "                max_len = max(max_len, len(tmp_str))\n",
    "                tmp_str = tmp_str[tmp_str.index(c)+1:] + c\n",
    "            else:\n",
    "                tmp_str += c\n",
    "        max_len = max(max_len, len(tmp_str))\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        if s == \" \":\n",
    "            return 1\n",
    "        n = len(s)\n",
    "        end,set = self.getdifferentIndex(s)\n",
    "        ans = end\n",
    "        start = 0\n",
    "        count = end\n",
    "        while end < n :\n",
    "            while end < n and s[end] in set:\n",
    "                set.remove(s[start])\n",
    "                start += 1\n",
    "                count-=1\n",
    "                \n",
    "\n",
    "            while end < n and s[end] not in set:\n",
    "                \n",
    "                set.add(s[end])\n",
    "                end += 1\n",
    "                count += 1\n",
    "                ans = max(count,ans)\n",
    "                \n",
    "        return ans\n",
    "         \n",
    "\n",
    "    \n",
    "    def getdifferentIndex(self,s):\n",
    "        n = len(s)\n",
    "        count = 0\n",
    "        occ = set()\n",
    "        for i in range(n):\n",
    "            if s[i] in occ:\n",
    "                break\n",
    "            else:\n",
    "                occ.add(s[i])\n",
    "                count += 1\n",
    "        return count,occ\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        left,n=0,len(s)\n",
    "        records=set()\n",
    "        ret=0\n",
    "        for i in range(n):\n",
    "            while s[i] in records:\n",
    "                records.remove(s[left])\n",
    "                left+=1\n",
    "            ret=max(ret,i-left+1)\n",
    "            records.add(s[i])\n",
    "        return ret\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
